[백준 4179] 불! (C++)

이 문제는 불이 났을 때, 지훈이가 가장 빨리 탈출할 수 있는 시간을 구하는 문제이다. 즉, 최단 탈출로의 길이를 구하는 문제라 할 수 있다.

하지만, 문제에서 지훈이는 벽인 곳과 불이 난 곳은 방문할 수 없다고 명시되어 있으므로 이를 고려해야 한다.

둘을 동시에 생각하는 것은 굉장히 복잡할 것 같다...

하지만, 불이 번지는 것은 그저 거리에 따라 특정 타일까지 도달하는 시간만 알면 쉽게 파악할 수 있을 것이다. 이는 BFS를 통해 손쉽게 알아낼 수 있을 것이다.

그리고, 지훈이는 임의의 타일로 이동하기 위해서는 그곳이 벽이 아니여야 하며, 불보다 먼저 도착해야 한다. 따라서, 지훈이의 경우에도 지훈이로부터 타일까지의 거리를 구하는 문제로 단순화 가능하므로, BFS를 이용하여 접근해야한다. 다만, 불까지의 거리보다 지훈이까지의 거리가 더 가까운 경우에만 큐에 삽입하도록 하면 될 것이다.

이를 코드로 옮기면 아래와 같다.

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

int r, c;
string board[1001];
int dist1[1001][1001], dist2[1001][1001];
queue<pair<int, int>> q1, q2;
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    for (int i = 0; i < 1001; i++) {
        fill(dist1[i], dist1[i] + 1001, -1);
        fill(dist2[i], dist2[i] + 1001, -1);
    }
    
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        cin >> board[i];
        for (int j = 0; j < c; j++) {
            if (board[i][j] == 'F') {
                q1.push({i, j});
                dist1[i][j] = 0;
            }
            else if (board[i][j] == 'J') {
                q2.push({i, j});
                dist2[i][j] = 0;
            }
        }
    }
    
    // 불 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 >= r || ny < 0 || ny >= c) continue;
            if (board[nx][ny] == '#' || dist1[nx][ny] >= 0) 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], nxt = dist2[x][y] + 1;
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
                cout << nxt;
                exit(0);
            }
            if (board[nx][ny] == '#' || dist2[nx][ny] >= 0) continue;
            if (dist1[nx][ny] != -1 && nxt >= dist1[nx][ny]) continue;
            q2.push({nx, ny});
            dist2[nx][ny] = nxt;
        }
    }
    
    cout << "IMPOSSIBLE";
}