[백준 5427] 불 (C++)

이 문제 역시 저번에 다루었던 백준 4179번 불!과 비슷한 문제이다. 다만, 테스트 케이스 여러 개가 주어진다는 점만 차이가 있다.

불이 매초 사방으로 번져나가고, 상근이가 건물을 탈출하려하는 상황이다. 이때, 최단 탈출 경로를 구하는 문제로, 불이 번지는 것을 구하려면 BFS를 써야하고, 상근이의 최단 탈출로를 구하기 위해 BFS를 써야하는 문제임을 파악할 수 있다.

다만, 불은 벽이 아닌 곳이면 모두 이동이 가능하고, 상근이는 벽인 곳과 불이 먼저 도착한 지점은 이동할 수 없으니 참고하자.

따라서, 상근이는 BFS를 구현할 때, 별도로 이동하려는 자리에 불이난 경우도 고려해야한다.

이를 바탕으로 코드를 작성하면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int tc, w, h;
string board[1000];
queue<pair<int, int>> q1, q2;
int dist1[1000][1000], dist2[1000][1000];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

string solve() {
    // 불 bfs
    while (!q1.empty()) {
        int x, y;
        tie(x, y) = q1.front();
        q1.pop();
        
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if (dist1[nx][ny] != -1 || board[nx][ny] == '#') continue;
            q1.push({nx, ny});
            dist1[nx][ny] = dist1[x][y] + 1;
        }
    }
    
    // 상근 bfs
    while (!q2.empty()) {
        int x, y;
        tie(x, y) = q2.front();
        q2.pop();
        
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) return to_string(dist2[x][y] + 1);
            if (dist2[nx][ny] != -1 || board[nx][ny] == '#') continue;
            if (dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[x][y] + 1) continue;
            q2.push({nx, ny});
            dist2[nx][ny] = dist2[x][y] + 1;
        }
    }
    
    return "IMPOSSIBLE";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> tc;
    while (tc--) {
        q1 = queue<pair<int, int>>();
        q2 = queue<pair<int, int>>();
        for (int i = 0; i < 1000; i++) {
            fill(dist1[i], dist1[i] + 1000, -1);
            fill(dist2[i], dist2[i] + 1000, -1);
        }
        
        cin >> w >> h;
        for (int i = 0; i < h; i++) {
            cin >> board[i];
            for (int j = 0; j < w; j++) {
                if (board[i][j] == '*') {
                    dist1[i][j] = 0;
                    q1.push({i, j});
                } else if (board[i][j] == '@') {
                    dist2[i][j] = 0;
                    q2.push({i, j});
                }
            }
        }
        
        cout << solve() << "\n";
    }
}