4206. 연구소 탈출

4206. 연구소 탈출

이전에 백준에서 비슷한 문제를 풀어본 적 있었던 것 같다.

예전에 백준에서 내가 풀 때는 맵을 두개를 만들고, 서로 비교하면서 문제를 풀었는데 풀고나서 다른 사람들 풀이를 보다가

BFS를 서로 번갈아가면서 풀었던 코드를 봤던게 생각났다.

이 문제도 마찬가지로 사람이 움직이고, 바이러스를 움직이면서 탈출 여부를 판단하면 된다.

사람이 맵의 끝자리에 있으면 탈출할 수 있다. (단, 그 자리가 탈출하기 직전에 바이러스에게 먹히면 안된다.)

바이러스에게 먹히면 안되는 것을 간과해서 문제를 틀렸었다.

그리고 탈출하지 못하면, 전체 맵을 탐색하면서 사람이 남아있는지를 파악한다. (맵에 3의 존재 여부)

3이 존재한다면, 좀비는 되지 않았지만 탈출할 수 없는 구조이기 때문에 CANNOT ESCAPE 를 출력하면 된다.

<정답 코드>

#include<iostream>
#include<queue>
 
using namespace std;
 
int map[8][8];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
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++)
    {
        int h, w;
        queue<pair<int, int>> v, s;
        cin >> h >> w;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                cin >> map[i][j];
                if (map[i][j] == 3)
                {
                    s.push({ i,j });
                }
                else if (map[i][j] == 2)
                {
                    v.push({ i,j });
                }
            }
        }
 
        int ex, ey;
        int dist[8][8] = { 0, };
        bool escape = false;
 
        //사람이 먼저 움직이고, 바이러스가 그 다음에 움직이고 -> 모두 BFS 이용
        while (!s.empty() || !v.empty())
        {
            int s_size = s.size();
            int v_size = v.size();
 
            //사람이 움직이는 BFS 
            for (int i = 0; i < s_size; i++)
            {
                int x = s.front().first;
                int y = s.front().second;
                s.pop();
 
                //탈출에 성공하는 경우
                if ((x == 0 || x == h - 1 || y == 0 || y == w - 1)&&map[x][y]!=2)
                {
                    ex = x, ey = y;
                    escape = true;
                    break;
                }
 
                for (int d = 0; d < 4; d++)
                {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if (nx >= 0 && ny >= 0 && nx < h && ny < w && dist[nx][ny] == 0 && map[nx][ny]==0)
                    {
                        map[nx][ny] = 3;
                        dist[nx][ny] = dist[x][y] + 1;
                        s.push({ nx,ny });
                    }
                }
            }
 
            if (escape)
            {
                break;
            }
 
            //바이러스가 움직이는 BFS
 
            for (int i = 0; i < v_size; i++)
            {
                int x = v.front().first;
                int y = v.front().second;
                v.pop();
 
                for (int d = 0; d < 4; d++)
                {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if (nx >= 0 && ny >= 0 && nx < h && ny < w && map[nx][ny] != 1 && map[nx][ny]!=2)
                    {
                        map[nx][ny] = 2;
                        dist[nx][ny] = dist[x][y] + 1;
                        v.push({ nx,ny });
                    }
                }
            }
 
        }
 
        //탈출했을 때
        if (escape)
        {
            cout << "#" << t << " " << dist[ex][ey] + 1 << "\n";
        }
        //탈출하지 못했을 때
        else
        {
            bool zombie = true;
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    //map 에 3이 남아있으면 좀비가 되지 않음.
                    if (map[i][j] == 3)
                    {
                        zombie = false;
                    }
                }
            }
 
            if (zombie)
            {
                cout << "#" << t << " " << "ZOMBIE\n";
            }
            else
            {
                cout << "#" << t << " " << "CANNOT ESCAPE\n";
            }
        }
    }
    return 0;
}