[ 백준 3055 ] 탈출 (C++)

백준의 탈출(3055) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 본인은 이 문제를 해결할 때, 물에 대한 맵을 하나 만들었고, 그 물에 대한 맵과 고슴도치의 움직임을 비교하면서

   해결해 나갔다.

2. 구체적으로 알아보자. 물은 1초마다 상하좌우로 퍼져나가게 된다. 즉, 현재 물이 있는 곳을 처음 Queue에 넣고 BFS-Leveling

   방법을 통해서 물이 매 초 마다 갈 수 있는 맵을 따로 만들어 주었다.

   문제를 보니, 처음 물이 시작하는 정점이 2개 이상일 때가 있기 때문에, BFS-Leveling 을 통해서 맵을 만들어 주었다.

  

3. 이제 고슴도치를 비버의 굴로 움직여보자. 3가지 조건에 대해서만 체크해보고 고슴도치를 움직여 주면 된다.

   조건 1 : 아직 탐색한 적이 없는 정점인가 ?

   조건 2 : 맵이 갈 수 있는 길인가?(바위가 아니인가?)

   조건 3 : 탐색하려고 하는 정점에 도달하는데 걸리는 시간이, 물이 도달한 시간보다 작은가?

   이 3가지에 대해서만 체크를 해주면 된다.

   조건 1, 2는 기본적으로 BFS를 구현할 때, 기본적으로 항상 해줘야 하는 것이고 조건 3만 조금 더 신경써주면 될 것이다.

   2번에서 만들어 놓은 물이 정점에 도달하는데 걸리는 시간을 체크해놓은 맵과 고슴도치가 현재 움직이는 시간을

   비교해서

   ' 한 정점에 물이 도착하는데 걸리는 시간 > 고슴도치의 현재 시간 + 1 ' 이라면 고슴도치가 갈 수 있는 것이다.

   고슴도치의 현재시간 + 1로 표현을 한 이유는, (x, y)에서 (nx, ny)로 움직일 때 1초가 더 걸리기 때문에

   (x, y)에서 (nx,ny)로 가려고 하는데, 만약 현재 시간 + 1초를 한 시간이 물이 도착하는데 걸리는 시간보다 작다면

   더 빠르다면 갈 수 있다 가 되는 것이다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int R, C;
int Water_MAP[MAX][MAX];
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
pair<int, int> Start_Pos, End_Pos;
queue<pair<int, int>> Water_Q;
 
void Input()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            Water_MAP[i][j] = 999;
        }
    }
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'S')
            {
                Start_Pos.first = i;
                Start_Pos.second = j;
            }
            else if (MAP[i][j] == 'D')
            {
                End_Pos.first = i;
                End_Pos.second = j;
            }
            else if (MAP[i][j] == '*')
            {
                Water_MAP[i][j] = 0;
                Water_Q.push(make_pair(i, j));
            }
        }
    }
}
 
void Make_WaterMap()
{
    while (Water_Q.empty() == 0)
    {
        int Qs = Water_Q.size();
        for (int i = 0; i < Qs; i++)
        {
            int x = Water_Q.front().first;
            int y = Water_Q.front().second;
            Water_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 < R && ny < C)
                {
                    if (MAP[nx][ny] == '.')
                    {
                        if (Water_MAP[nx][ny] > Water_MAP[x][y] + 1)
                        {
                            Water_MAP[nx][ny] = Water_MAP[x][y] + 1;
                            Water_Q.push(make_pair(nx, ny));
                        }
                    }
                }
            }
        }
    }
}
 
void Move()
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(Start_Pos.first, Start_Pos.second), 0));
    Visit[Start_Pos.first][Start_Pos.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_Pos.first && y == End_Pos.second)
        {
            cout << Cnt << 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 < R && ny < C)
            {
                if (Visit[nx][ny] == false && MAP[nx][ny] != 'X' && Water_MAP[nx][ny] > Cnt + 1)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                }
            }
        }
    }
    cout << "KAKTUS" << endl;
}
 
void Solution()
{
    Make_WaterMap();
    Move();
}
 
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;
}