[ 백준 2424 ] 부산의 해적 (C++)

백준의 부산의해적(2424) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 본인은 가장 먼저 해적에 대한 맵을 만들어 주었다. 해적은 수아의 움직임에 따라서 움직일수도 있고, 안움직일 수도 있지만

   해적이 가장 빠르게 움직일 수 있는 값은 정해져있다.

   다음과 같은 상황을 예시로 알아보자.

  

   이런 경우에 위에서 표시된 빨간색점에 해적은 몇초에 갈 수 있을까 ??

   2초에 갈수도 있고, 중간에 움직이지 않는 경우를 생각해보면 3초에 갈수도, 4초에 갈수도, 5초에 갈수도 있다

   그렇다면 수아가 2초에 파란점을 갈 수 있을까 ? 3초에 파란점을 갈 수 있을까 ?

   수아는 저 파란점에 갈 수가 없다. 해적이 빨간점에 3초에 올 수도, 4초에 올 수도, 5초에 올 수도 있지만 가장 빠르게 온다면

   2초에 올 수도 있기 때문에, 2초에 해적과 일직선상에 있어서 수아는 죽게 된다.

   즉, 해적이 특정 좌표와 몇 초에 일직선 상에 존재하는지를 저장하는 맵을 만들어 주었다.

   말이 조금 이상한데 쉽게 생각하면 다음과 같다.

  

   해적이 위와 같이 위치하게 된다면, 결과적으로 수아는 해적과 같은 좌표에 있어야 죽는 것이 아닌, 같은 행 혹은

   같은 열에만 있어도(중간에 섬이 없다고 가정하면) 죽기 때문에 해적이 해당 좌표를 최소시간 몇 초에 바라볼 수 있는지

   맵을 작성한다는 것이다. 즉, 위의 그림과 같은 경우에는 다음과 같이 맵이 그려질 것이다.

   

   즉, 위의 값들은 "해당 좌표에 도달하는 최단시간"을 나타낸 것이 아닌, "해적이 최소시간에 바라볼 수 있는 시간"(?)을

   나타낸 것이다. 말로 표현하려니 조금 이상하다..

  

2) 해적의 맵을 만드는 과정에 대해서 알아보자.

   가장 먼저, 너비 우선 탐색(BFS)로 해적이 각 좌표에 갈 수 있는 최소 시간을 구해보았다.

  

   이 맵을 예시로 알아보자. 가장 먼저, 해적이 각 좌표에 갈 수 있는 최소 시간을 구해서 값을 넣어준다면 다음과 같이

   표가 채워질 것이다.

  

   그럼 이 맵을 토대로, 각 행과 각 열에서 최소값을 찾아서 설정해 주는 것이다.

   하지만, 이 맵에서 그대로 갱신을 하게 되면, 그 다음에 진행되는 행, 혹은 그 다음에 진행될 열의 값들에 지장이

   생기므로, 위의 값들을 저장할 맵을 하나 만들고, 해적의 움직임을 저장할 또 하나의 맵을 선언해서 저장해 주어야 한다.

   먼저 0행부터 봐보도록 하자. 값을 설정해줄 초기 최소값은 무한대로 초기화를 시켜놓는다.

   (지금부터 이 값을 'Min' 값이라고 하겠음.)

   1. (0, 0)의 값과 Min 값을 비교한다. 0 < 무한대 이므로 (0, 0)의 값은 0으로 설정. 동시에 Min 값을 0으로 설정.

   2. (0, 1)의 값과 Min 값을 비교한다. 1 > 0 이므로, (0, 1)의 값은 0으로 설정.

   3. 2번에 의한 계산과 마찬가지로 (0, 2) ~ (0, 5) 까지 모두 '0'으로 설정됨.

   여기까지 하면, 하나의 행에 대한 계산이 완료된 것이 아니다. 역순으로도 한번 체크를 해주어야 한다.

   왜 그럴까 ?? 해적의 위치를 아래 그림과 같이 반대 위치라고 생각해보자.

  

   이 경우에, 해적위치에서 BFS탐색을 돌려서, 각 좌표마다 갈 수 있는 최단거리를 설정해주면 다음과 같이 될 것이다.

  

   그리고 위에서 말한 1 ~ 3번 과정을 그대로 다시한번 해보자.

   1. (0, 0)의 값과 Min 값을 비교한다. 5 < 무한대 이므로 (0, 0)의 값은 5으로 설정. 동시에 Min 값을 5로 설정.

   2. (0, 1)의 값과 Min 값을 비교한다. 4 < 5 이므로, (0, 1)의 값은 4로 설정.

   3. 2번에 의한 계산과 마찬가지로 (0, 2) ~ (0, 5) 까지 순차적으로 '3', '2', '1', '0' 이 설정됨.

   뭔가 계산이 이상하다. 분명히, 0행은 0초로 값이 설정되어야 맞지만, 위와 같은 경우 제대로 설정되지가 않는다.

   따라서, 역순으로도 한번 해주는 것이다. 위의 과정을 !

   1. (0, 5)의 값과 Min 값을 비교한다. 0 < 무한대 이므로 (0, 5)의 값은 0으로 설정. 동시에 Min값을 0으로 설정.

   2. (0, 4)의 값과 Min 값을 비교한다. 1 > 0 이므로 (0, 4)의 값은 0으로 설정.

   3. 2번에 의한 계산과 마찬가지로 (0, 3) ~ (0, 0) 은 모두 '0'으로 설정.

   이렇게 계산을 정순으로 한번, 역순으로 한번 해주어야 한다.

   또한, 방금 위에서 설명한 부분에는 중간에 섬이 없는데, 섬이 있는 경우에는 Min값을 다시 무한대로 설정해 주어야 한다.

   왜냐하면, 그 전의 최소값에 그 다음 좌표가 영향을 미치지 않기 때문에 섬이 있을 경우에는 최소값으로 저장해 주어야 한다.

  

   열을 설정하는 과정도 행과 굉장히 비슷한데, 한가지를 더 유의해 주어야 한다.

   이미, 위에서 한 '행에 대한 계산' 때문에 해적맵이 어느정도는 값이 설정되어 있는 상태일 것이다.

   이 값들을 다시 열에 대한 값들을 비교해서 맵을 채워 넣어야 하기 때문에, 기존에 설정되어 있는 값들과 지금부터 할

   열에 대한 값들을 비교해서 더 작은 값으로 설정을 해주면 된다.

  

3) 이런식으로 해적의 맵을 모두 만들었다면, 이제 수아를 움직여 주기만 하면 된다.

   이 부분 또한, 본인은 너비우선탐색(BFS)으로 구현해 주었고, 탐색 조건은, 만들어 놓은 해적맵과 비교를 하면서

   "현재 좌표에 수아가 도달했을 때 걸리는 시간이, 해적이 가장 빠르게 움직였을 때, 해당 좌표를 바라볼 수 있는 시간 보다

    더 빠르다면" 탐색을 진행해 주었다.

  

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 700
#define INF 987654321
using namespace std;
 
int N, M;
char MAP[MAX][MAX];
int H_MAP[MAX][MAX];
int HC_MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
pair<int, int> Start, End, HaeJuk;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'Y') 
            {
                Start.first = i;
                Start.second = j;
                MAP[i][j] = '.';
            }
            else if (MAP[i][j] == 'T')
            {
                End.first = i;
                End.second = j;
                MAP[i][j] = '.';
            }
            else if (MAP[i][j] == 'V')
            {
                HaeJuk.first = i;
                HaeJuk.second = j;
                MAP[i][j] = '.';
            }
            HC_MAP[i][j] = INF;
        }
    }
}
 
void Arrange_MAP()
{
    for (int i = 0; i < N; i++)
    {
        int MinValue = INF;
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == 'I')
            {
                MinValue = INF;
                H_MAP[i][j] = INF;
                continue;
            }
            MinValue = Min(MinValue, HC_MAP[i][j]);
            H_MAP[i][j] = MinValue;
        }
 
        MinValue = INF;
        for (int j = M - 1; j >= 0; j--)
        {
            if (MAP[i][j] == 'I')
            {
                MinValue = INF;
                H_MAP[i][j] = INF;
                continue;
            }
            MinValue = Min(MinValue, HC_MAP[i][j]);
            H_MAP[i][j] = Min(MinValue, H_MAP[i][j]);
        }
    }
 
    for (int j = 0; j < M; j++)
    {
        int    MinValue = INF;
        for (int i = 0; i < N; i++)
        {
            if (MAP[i][j] == 'I') 
            {
                MinValue = INF;
                H_MAP[i][j] = INF;
                continue;
            }
            MinValue = Min(MinValue, HC_MAP[i][j]);
            H_MAP[i][j] = Min(MinValue, H_MAP[i][j]);
        }
        
        MinValue = INF;
        for (int i = N - 1; i >= 0; i--)
        {
            if (MAP[i][j] == 'I')
            {
                MinValue = INF;
                H_MAP[i][j] = INF;
                continue;
            }
            MinValue = Min(MinValue, HC_MAP[i][j]);
            H_MAP[i][j] = Min(MinValue, H_MAP[i][j]);
 
        }
    }
}
 
void Make_HaeJuk_Map()
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(HaeJuk.first, HaeJuk.second));
    HC_MAP[HaeJuk.first][HaeJuk.second] = 0;
    int Level = 0;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == '.' && HC_MAP[nx][ny] > HC_MAP[x][y] + 1)
                {
                    HC_MAP[nx][ny] = HC_MAP[x][y] + 1;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
    Arrange_MAP();
}
 
void Move_SooA()
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(Start.first, Start.second), 0));
    Visit[Start.first][Start.second] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == End.first && y == End.second)
        {
            cout << "YES" << endl;
            return;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == '.' && Visit[nx][ny] == false)
                {
                    if (H_MAP[nx][ny] > Cnt + 1)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                    }
                }
            }
        }
    }
    cout << "NO" << endl;
}
 
void Solution()
{
    Make_HaeJuk_Map();
    Move_SooA();
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}