[ 백준 16954 ] 움직이는 미로 탈출 (C++)

백준의 움직이는 미로탈출(16954) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 벽이 1초마다 한칸씩 아래로 내려오는 상황에서, 도착점에 도달할 수 있는지 구해야 하는 문제이다.

   먼저, 본인은 이 문제를 해결하기 위해서 먼저 벽의 맵을 따로 만들어 주었다.

   벽의 맵은 3차원으로 이루어져있으며 Wall_MAP[a][b][c] = '.' or '#' 의 의미는

   'a'초 일 때, (b, c)는 빈 공간이거나 벽입니다 를 의미한다.

   이 후에, 사람을 이 벽의 맵과 비교하면서 움직이는 식으로 구현을 해 주었다.

  

2) 본격적인 구현에 들어가보자. 먼저, 벽의 맵을 만들어보자.

   벽의 맵을 만들기 위해서 본인은 먼저 입력과 동시에 벽의 위치를 Vetor에 저장해 주었다.

   이 Vector에 저장된 각각의 좌표들을 이용해서 3차원 Wall_MAP에 저장해 주었다.

   이 후, 사람을 움직이는 것은 BFS탐색을 통해서 구현해 주었다.

   BFS탐색을 할 때에는 2가지를 고려해 주었다.

   먼저 첫 번째는 현재 (x, y)에 있고, t초라고 가정할 때, t + 1초에 (x + 방향, y + 방향) 으로 움직였을 때, 그 칸이

   벽이 없는지(Wall_MAP[t+1][x+방향][y+방향] == '.') 를 고려해 주었다.

   사실 처음에는 이거 한가지만 비교를 해 주었는데, 이러면 틀리게 된다. 얼핏보면 저 조건만 비교해준다면 맞을 것

   같지만 예제입력2를 한번 봐보도록 하자.

  

    예제입력2는 위와같은 형태이고, 시작점을 O로 표시해보았다.

    그렇다면 벽의 맵을 한번 생각해보자. 0초일 때 벽의 맵은 위와 같은 형태일 것이고, 1초일 때를 생각해보자.

   

    1초일 때는 다음과 같은 형태이다. 그렇다면, 여기서 빨강색으로 표시된 (6, 0)과 (6, 1)에 주목해보자.

    분명, 1초일 때, 저 (6, 0)과 (6, 1)은 빈 공간이라서 사람이 갈 수 있는 곳으로 표시가 되어있다.

    하지만 ! 0초일 때의 맵을 한번 봐보자. 사람이 1초에 저기로 갈 수 있을까?? 딱 봐도 갈 수 없다는 것을 알 수 있다.

    즉, " 사람이 이동하려는 곳의 좌표가 현재 시간에 벽이면 움직일 수 없다 ! " 라는 것을 알 수 있다.

    이 2가지만 생각해 주면 된다. 또한, 일반적인 문제들과 같이 한번 방문한 지점을 재방문 하지 못하게 하면 안된다.

   

    마지막으로 BFS탐색의 종료조건은 다음과 같다. 사람이 가장 오른쪽 위의 좌표에 도착하는 경우는 물론이고,

    사람이 가장 윗줄로만 도착하더라도 사실 도착지에 도착할 수 있다. 사람이 어떻게 어떻게 올라가서 (0, 0)까지 갔다고

    생각해보자. 당연히 더 이상 내려올 벽은 없을 것이고, (0, 0)에서 (0, 7)까지 이동하는 것도 탐색에 추가시킨다면

    시간 낭비일 것이다. 사람이 가장 윗줄에만 도착한다면 (0, 7)이 아니더라도 도착지에 도착할 수가 있다.

    또 하나는 현재 사람이 있는 줄보다 위에 있는 줄을 모두 비교했을 때 벽이 더이상 없는 경우이다.

    모든 맵이 '.' 으로만 입력되어 있는 예제입력1을 봐보도록 하자. 굳이 탐색을 해야 도착하는지 알 수 있을까??

    아니다. 무조건 도착점에 도달할 수가 있다. 왜냐하면 현재 사람이 있는 지점 윗줄들에 벽이 하나도 없기 때문이다.

    이러한 맵을 생각해보자. 1초 후에 사람이 갈 수 있는 곳과 벽의 상태를

     표시해보면 다음과 같아진다.

    

      1초 후에 사람이 움직일 수 있는 곳은 O친 2곳이 될 것이며, 벽은 저렇게 내려오게 될 것이다.

      그렇다면, 저 상태에서 탐색을 더 해봐야 도착점에 도착하는지 알 수 있을까?? 아니다. 무조건 도착할 수 있다는 것을

      알 수 있다. 왜냐하면 사람이 있는 지점보다 윗줄에 벽이 더 이상 존재하지 않기 때문이다.

      따라서 본인은

      1. 사람이 제일 윗줄에 도착했을 경우

      2. 사람이 있는 좌표를 기준으로 그 윗줄에 벽이 하나도 없는 경우

      이 2가지를 종료조건으로 만들어 주었다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
char MAP[MAX][MAX];
char Wall_MAP[MAX][MAX][MAX];
vector<pair<int, int>> Wall_V;
 
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1, 0 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1, 0 };
 
void Input()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == '#')
            {
                Wall_MAP[0][i][j] = '#';
                Wall_V.push_back(make_pair(i, j));
            }
        }
    }
    for (int t = 0; t < MAX; t++)
    {
        for (int i = 0; i < MAX; i++)
        {
            for (int j = 0; j < MAX; j++)
            {
                if (Wall_MAP[t][i][j] == '#') continue;
                Wall_MAP[t][i][j] = '.';
            }
        }
    }
}
 
void Make_Wall_MAP()
{
    for (int i = 0; i < Wall_V.size(); i++)
    {
        int x = Wall_V[i].first;
        int y = Wall_V[i].second;
        int Time = 1;
 
        while (1)
        {
            int nx = x + 1;
            int ny = y;
            if (nx >= MAX) break;
            
            Wall_MAP[Time][nx][ny] = '#';
            Time++;
            x = nx;
            y = ny;
        }
    }
}
 
void Print()
{
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            for (int k = 0; k < 8; k++)
            {
                cout << Wall_MAP[i][j][k] << " ";
            }
            cout << endl;
        }
        cout << "#######################################" << endl;
    }
}
 
bool Can_Finish(int x, int T)
{
    for (int i = x - 1; i >= 0; i--)
    {
        for (int j = 0; j < MAX; j++)
        {
            if (Wall_MAP[T][i][j] == '#') return false;
        }
    }
    return true;
}
 
int BFS(int a, int b)
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(a, b), 0));
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int t = Q.front().second;
        Q.pop();
 
        if (x == 0) return 1;
        else
        {
            if (Can_Finish(x, t) == true) return 1;
        }
        
        for (int i = 0; i < 9; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nt = t + 1;
 
            if (nx >= 0 && ny >= 0 && nx < MAX && ny < MAX)
            {
                if (Wall_MAP[nt][nx][ny] == '.' && Wall_MAP[t][nx][ny] == '.')
                {
                    Q.push(make_pair(make_pair(nx, ny), nt));
                }
            }
        }
    }
    return 0;
}
 
bool Wall_State()
{
    for (int i = 0; i < 7; i++)
    {
        int Cnt = 0;
        for (int j = 0; j < MAX; j++)
        {
            if (MAP[i][j] == '#') Cnt++;
        }
        if (Cnt == 8) return false;
    }
    return true;
}
 
//(x,y) 말고 
void Solution()
{
    if (Wall_V[0].size() == 0)
    {
        cout << 1 << endl;
        return;
    }
    if (Wall_State() == false)
    {
        cout << 0 << endl;
        return;
    }
    Make_Wall_MAP();
    cout << BFS(7, 0) << endl;
}
 
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;
}