[BOJ_C++] 5427번: 불

CODE

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int tc, w, h;
string board[1002];
int dist[1002][1002];
int fire_dist[1002][1002];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> tc;
    while(tc--){
        queue<pair<int, int>> fire;
        queue<pair<int, int>> q;
        bool flag = false;

        memset(dist, -1, sizeof(dist));
        memset(fire_dist, -1, sizeof(fire_dist));

        cin >> w >> h;
        for(int i=0; i<h; i++)
            cin >> board[i];
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(board[i][j] == '@'){
                    q.push(make_pair(i, j));
                    dist[i][j] = 0;
                } 
                if(board[i][j] == '*'){
                    fire.push(make_pair(i,j));
                    fire_dist[i][j] = 0;
                }
            }
        }

        while(!fire.empty()){
            auto cur = fire.front(); fire.pop();
            for(int dir=0; dir<4; dir++){
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if(fire_dist[nx][ny] != -1 || board[nx][ny] == '#') continue;
                fire_dist[nx][ny] = fire_dist[cur.X][cur.Y] + 1;
                fire.push(make_pair(nx, ny));
            }
        }
        
        while(!q.empty()){
            auto cur = q.front(); q.pop();
            for(int dir=0; dir<4; dir++){
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(nx < 0 || nx >= h || ny < 0 || ny >= w){
                    cout << dist[cur.X][cur.Y] + 1 << '\n';
                    flag = true; break;
                }
                if(board[nx][ny] == '#' || board[nx][ny] == '*') continue;
                if(dist[nx][ny] != -1) continue;
                if((dist[cur.X][cur.Y] + 1 >= fire_dist[nx][ny]) && fire_dist[nx][ny] != -1) continue;
                dist[nx][ny] = dist[cur.X][cur.Y] + 1;
                q.push(make_pair(nx, ny));
            }
            if(flag) break;
        }
        if(!flag) cout << "IMPOSSIBLE\n";
    }

    return 0;
}

풀이

1. 불의 전파 시간과 상근이의 이동 시간을 측정하기 위한 dist와 fire_dist를 각각 -1로 초기화 한다. 
2. 빌딩의 지도를 입력받으며 불의 위치와 상근이의 위치를 큐에 넣고 시작의 의미로 거리를 0으로 초기화 한다.
3. 먼저 불에 대한 BFS를 돌며 불의 전파 시간에 대하여 알아둔다. (상근이는 불이 붙은 곳에 가지 못하기 때문)
4. 이후 상근이에 대한 BFS를 돈다.
   1. 만약 범위를 벗어났다면 탈출에 성공했다는 의미로 탈출한 시간을 출력한다.
   2. 만약 다음 위치가 벽이거나 불이라면 다음 위치를 탐색한다.
   3. 만약 다음 위치가 불이 옮겨 붙은 곳이라면 다음 위치를 탐색한다.
   4. 아니면 다음 위치에 전파 시간을 넣고 큐에 다음 위치를 넣어 BFS 탐색을 진행한다.
5. 만약 위에서 아무 값도 출력하지 못해 flag가 false라면 탈출이 불가능한 것이므로 IMPOSSIBE을 출력한다.

결과