불!

처음에 DFS로 모든 경로를 탐색하는 방향으로 할려고 했으나 실패함.

이 문제는 지훈이가 불보다 빨리 나가야 하는 게임이다.

가중치가 같은 경우의 최단거리 문제이기 때문에

BFS를 사용해야한다.

불은 이런식으로 BFS가 퍼져 나갈 것이다.

지훈이는 이런식으로 퍼져 나갈 수 있다.

불의 BFS, 지훈이의 BFS를 다 돌리고 난뒤,

지훈이의 BFS의 y, x의 좌표의 값이 불의 BFS의 y, x좌표의 값보다 "작다면" 빨리 탈출 할 수 있는 경로이다.

크거나 같다면 못가는 부분임.

이런식으로 나갈 수 있다.

cpp 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 1004
const int INF = 987654321;

int n, m, sy, sx;
int F = int('F'), W = int('#'), J = int('J'), R = int('.');
int arr[MAX][MAX], FireCheck[MAX][MAX], PersonCheck[MAX][MAX];
int dy[4] = {0, 1, 0, -1}, dx[4] = {-1, 0, 1, 0};
int ret;
bool In(int a, int b)
{
    return 0 <= a && a < n && 0 <= b && b < m;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    queue<pair<int, int>> q;
    cin >> n >> m;
    fill(&FireCheck[0][0], &FireCheck[0][0] + MAX * MAX, INF);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            char c;
            cin >> c;
            arr[i][j] = int(c);
            if (arr[i][j] == F)
            {
                FireCheck[i][j] = 1;
                q.push({i, j});
            }
            else if (arr[i][j] == J)
            {
                sy = i;
                sx = j;
            }
        }
    }

    // 불의 최단거리
    while (!q.empty())
    {
        pair<int, int> p = q.front();
        q.pop();
        int y = p.first;
        int x = p.second;
        for (int i = 0; i < 4; ++i)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (!In(ny, nx)) continue;
            if (FireCheck[ny][nx] != INF || arr[ny][nx] == W) continue;
            FireCheck[ny][nx] = FireCheck[y][x] + 1;
            q.push({ny, nx});
        }
    }

    // 지훈 최단거리
    PersonCheck[sy][sx] = 1;
    q.push({sy, sx});
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        if (x == m - 1 || y == n - 1 || x == 0 || y == 0)
        {
            ret = PersonCheck[y][x];
            break;
        }
        for (int i = 0; i < 4; ++i)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (!In(ny, nx)) continue;
            if (PersonCheck[ny][nx] || arr[ny][nx] == W) continue;
            if (FireCheck[ny][nx] <= PersonCheck[y][x] + 1) continue;
            PersonCheck[ny][nx] = PersonCheck[y][x] + 1;
            q.push({ny, nx});
        }
    }

    if (ret != 0) cout << ret << endl;
    else cout << "IMPOSSIBLE" << endl;

    return 0;
}
```