https://www.acmicpc.net/problem/4179

✍️ 첫번째 접근

흔히 알고있는 BFS를 적용할 수 있는 문제이다. BFS를 시작하는 종류가 한 종류가 아니라 두 종류로 생각해서 풀면 된다.
지훈이가 불에 타기 전에 미로에서 탈출할 수 있는지에 대한 BFS와 불이 확산되는 거에 대한 BFS를 돌리면 된다.
필자는 불에 대한 BFS를 먼저 돌려서 각 지점에 불이 확산되는 시간을 구하고, 지훈이에 대한 BFS를 돌리는데 지훈이가 처음 방문하는 칸에 이미 불이 존재하거나 지훈이가 그 칸을 방문함과 동시에 불도 확산된다면 그 칸은 못 가게 하였다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[1002];
int dist1[1002][1002];
int dist2[1002][1002];
int r,c;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> r >> c;
    for(int i = 0; i < r; i++) {
        cin >> board[i];
    }
    for(int i = 0; i < r; i++) {
        fill(dist1[i],dist1[i]+c,-1);
        fill(dist2[i],dist2[i]+c,-1);
    }
    queue<pair<int,int> > Q1;
    queue<pair<int,int> > Q2;
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            if(board[i][j] == 'F') {
                Q1.push(make_pair(i,j));
                dist1[i][j] = 0;
            }
            if(board[i][j] == 'J') {
                Q2.push(make_pair(i,j));
                dist2[i][j] = 0;
            }
        }
    }

    while(!Q1.empty()) {
        pair<int,int> cur = Q1.front();
        Q1.pop();

        for(int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= r || ny < 0 || ny >= c)
                continue;
            if(dist1[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;
            dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
            Q1.push(make_pair(nx,ny));
        }
    }

    while(!Q2.empty()) {
        pair<int,int> cur = Q2.front();
        Q2.pop();

        for(int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= r || ny < 0 || ny >= c) {
                cout << dist2[cur.X][cur.Y] + 1;
                return 0;
            }
            if(dist2[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;
            if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1)
                continue;
            dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
            Q2.push(make_pair(nx,ny));
        }
    }
    cout << "IMPOSSIBLE";


    return 0;
}