BOJ - 5427 - 불

ggh·2022년 8월 29일

BFS boj cpp ps 너비우선탐색

백준

목록 보기

66/112

BOJ - 5427 - 불

문제

5427번: 불

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

구현

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

// map
int n, m;
int map[1004][1004];
int Jvisited[1004][1004];
int Fvisited[1004][1004];
// joy
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

// x, y
int x, y, jx, jy, fx, fy;
// q 
queue<pair<int, int>> fq;
queue<pair<int, int>> jq;
vector<string> v;
int main()
{
    int num;
    cin >> num;
    for(int k=0; k < num; k++)
    {
        
        cin >> m >> n;
        // map 이진화 
        for(int i=0; i < n; i++)
        {
            string str;
            cin >> str;
            for(int j=0; j < m; j++)
            {
                char tmp = str[j];
                if(tmp == '#')
                    map[i][j] = 1;
                else if(tmp == '.')
                    map[i][j] = 0;
                else if(tmp == '@')
                {
                    jy = i;
                    jx = j;
                }
                else
                {
                    fq.push({i, j});
                    Fvisited[i][j] = 1;
                }
            }
        }
        
        jq.push({jy, jx});
        Jvisited[jy][jx] = 1;

        // 최단거리 
        while (fq.size())
        {
            fx = fq.front().second;
            fy = fq.front().first;
            fq.pop();

            for(int i=0; i < 4; i++)
            {
                int ny = fy + dy[i];
                int nx = fx + dx[i];
                
                if(ny < 0 || nx < 0|| ny >= n || nx >= m)
                    continue;
                // 벽일 경우, 이미 방문 했을 경우 
                if(map[ny][nx] || Fvisited[ny][nx])
                    continue;
                Fvisited[ny][nx] = Fvisited[fy][fx] + 1;
                fq.push({ny, nx});
            }
        }

        while(jq.size())
        {
            y = jq.front().first;
            x = jq.front().second;
            jq.pop();

            for(int i=0; i < 4; i++)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];
                
                if(ny < 0 || nx < 0|| ny >= n || nx >= m)
                    continue;    
                // 벽일 경우, 이미 방문 했을 경우 
                if(map[ny][nx] || Jvisited[ny][nx])
                    continue;
                Jvisited[ny][nx] = Jvisited[y][x] + 1;
                jq.push({ny, nx});
            }
        }
        // 불을 피해가는 최단거리 값
        for(int i=0; i < n; i++)
            for(int j=0; j < m; j++)
            if(Jvisited[i][j] >= Fvisited[i][j] && Fvisited[i][j])
                    Jvisited[i][j] = 0;    

        long long min = 9999999999;
        for(int i=0; i < n; i++)
        {
            if(i == 0 || i == n-1)
            {
                for(int j=0; j < m; j++)
                    if(min > Jvisited[i][j] && Jvisited[i][j])
                        min = Jvisited[i][j];
            }
            else
            {
                if(min > Jvisited[i][0] && Jvisited[i][0])
                    min = Jvisited[i][0];
                else if(min > Jvisited[i][m-1] && Jvisited[i][m-1])
                    min = Jvisited[i][m-1];
            }
        }

        // map 출력
        // cout << "---------------" << endl;
        // for(int i=0; i < n; i++)
        // {
        //     for(int j=0; j < m; j++)
        //     {
        //        cout << Jvisited[i][j] << " ";
        //     }   
        //     cout << endl;
        // }
        // 출구가 존재하면
        if(min != 9999999999)
            v.push_back(to_string(min));
        else
            v.push_back("IMPOSSIBLE");
        for(int i=0; i < n+4; i++)
            for(int j=0; j < m+4; j++)
            {
                Fvisited[i][j] = 0;
                Jvisited[i][j] = 0;
                map[i][j] = 0;
            }
        // 초기화      
        while(jq.size())
            jq.pop();
        while(fq.size())
        fq.pop();
        
    }
    for(auto &el : v)
        cout << el << endl;

    return 0;
}