4193. 수영대회 결승전

4193. 수영대회 결승전

기존의 BFS 문제에서 조금 달라졌다. 소용돌이가 생겼다 없어졌다 하는 주기가 반복되는 문제였다.

소용돌이가 없어져서 소용돌이 속으로 움직일 수 있는 시간이 3초,6초,9초.. 이런식으로 반복된다.

따라서 다익스트라를 이용해서 가중치를 주는 방식으로 문제를 풀었다.

단 소용돌이 이전 단계에서 현재 dist 값을 3가지로 나눠서 문제를 풀었다.

dist%3==0 , dist%3==1, dist%3==2 인 경우로 나누었다.

예를 들어 0초인 경우에는 dist%3==0 이기 때문에 소용돌이로 이동하기 위해선 3초를 기다려야 한다. 따라서 움직이면 3을 추가한다.

1초인 경우에는 dist%3==1 이고, 소용돌이로 이동하기 위해서는 2초만 기다리면 된다.

이런식으로 케이스를 나누어서 다익스트라를 적용해서 풀 수 있었다.

<정답 코드>

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int INF = 987654321;
int n;
int map[15][15];
bool chk[15][15];
int dist[15][15] = { 0, };
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
void init()
{
    for (int i = 0; i < 15; i++)
    {
        for (int j = 0; j < 15; j++)
        {
            map[i][j] = 0;
            dist[i][j] = INF;
            chk[i][j] = false;
        }
    }
}
int main()
{
    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        init();
        cin >> n;
        for (int i = 0; i<n; i++)
        {
            for (int j = 0; j<n; j++)
            {
                cin >> map[i][j];
            }
        }
 
        int sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
 
        priority_queue<pair<int, pair<int, int>>> q;
        dist[sx][sy] = 0;
        q.push({ -dist[sx][sy],{sx,sy} });
 
        while (!q.empty())
        {
            int x = q.top().second.first;
            int y = q.top().second.second;
            int cost = -q.top().first;
            q.pop();
 
            if (cost > dist[x][y])
            {
                continue;
            }
 
            for (int d = 0; d < 4; d++)
            {
                int nx = x + dx[d];
                int ny = y + dy[d];
                int w;
                if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny]!=1)
                {
                    if (map[nx][ny] == 0 && dist[nx][ny] > cost+1)
                    {
                        dist[nx][ny] = cost + 1;
                        q.push({ -dist[nx][ny],{ nx,ny } });
                    }
                    else
                    {
                        if (dist[x][y] % 3 == 0 && dist[nx][ny] > cost+3)
                        {
                            dist[nx][ny] = cost + 3;
                            q.push({ -dist[nx][ny],{ nx,ny } });
                        }
                        else if (dist[x][y] % 3 == 1 && dist[nx][ny] > cost + 2)
                        {
                            dist[nx][ny] = cost + 2;
                            q.push({ -dist[nx][ny],{ nx,ny } });
                        }
                        else if (dist[x][y] % 3 == 2 && dist[nx][ny] > cost + 1)
                        {
                            dist[nx][ny] = cost + 1;
                            q.push({ -dist[nx][ny],{ nx,ny } });
                        }
                    }
 
                }
            }
        }
 
        if (dist[ex][ey] == INF)
        {
            dist[ex][ey] = -1;
        }
 
        cout << "#" << t << " " << dist[ex][ey]<< "\n";
    }
    return 0;
}