BOJ 4179 C++

코드

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define X first
#define Y second

string level[1001]; // 미로의 행 정보를 저장할 배열
int Fdis[1001][1001]; // 불 이동 거리 저장 배열
int Jdis[1001][1001]; // 지훈이 이동 거리 저장 배열
int dx[4] = { 1, 0, -1, 0 }; // 수평 이동을 위한 배열
int dy[4] = { 0, 1, 0, -1 }; // 수직 이동을 위한 배열
queue<pair<int, int>> fire; // 불 위치를 저장할 큐
queue<pair<int, int>> jih; // 지훈이 위치를 저장할 큐
int r, c; // 미로의 행과 열 길이

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> c;

    // 초기화 작업 진행
    for (int i = 0; i < r; i++) {
        fill(Fdis[i], Fdis[i] + c, -1);
        fill(Jdis[i], Jdis[i] + c, -1);
    }

    // 미로 정보 입력 받기
    for (int i = 0; i < r; i++)
    {
        cin >> level[i];
        for (int j = 0; j < c; j++)
        {
            if (level[i][j] == 'F')
            {
                fire.push({ i, j });
                Fdis[i][j] = 0;
            }
            if (level[i][j] == 'J')
            {
                jih.push({ i, j });
                Jdis[i][j] = 0;
            }
        }
    }

    // BFS 실행: 불에 대한 이동 거리 계산
    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 >= r || nx < 0 || ny >= c || ny < 0) continue;

            // 이미 불이 도달하거나 벽인 경우 계속 (불이 이동할 수 없음)
            if (Fdis[nx][ny] >= 0 || level[nx][ny] == '#') continue;

            // 계산된 Fdis 저장 후 이동할 위치 push
            Fdis[nx][ny] = Fdis[cur.X][cur.Y] + 1;
            fire.push({ nx, ny });
        }
    }

    // BFS 실행: 지훈이에 대한 이동 거리 계산
    while (!jih.empty())
    {
        auto cur = jih.front(); jih.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            // 지훈이가 범위를 벗어난 경우 출력 후 종료
            if (nx >= r || nx < 0 || ny >= c || ny < 0)
            {
                cout << Jdis[cur.X][cur.Y] + 1;
                return 0;
            }

            // 이미 지훈이가 도달하거나 벽인 경우 계속 (지훈이가 이동할 수 없음)
            if (Jdis[nx][ny] >= 0 || level[nx][ny] == '#') continue;

            // 불이 지훈이보다 먼저 도달하고 도달 했을경우
            if (Fdis[nx][ny] <= Jdis[cur.X][cur.Y] + 1 && Fdis[nx][ny] != -1) continue;

            // 계산된 Jdis 저장 후 이동할 위치 push
            Jdis[nx][ny] = Jdis[cur.X][cur.Y] + 1;
            jih.push({ nx, ny });
        }
    }

    // 모든 탈출 경로를 시도해 본 후 도달하지 못하면 IMPOSSIBLE 출력
    cout << "IMPOSSIBLE";
    return 0;
}

문제에서 중요한 부분은

// 불이 지훈이보다 먼저 도달하고 도달 했을경우
            if (Fdis[nx][ny] <= Jdis[cur.X][cur.Y] + 1 && Fdis[nx][ny] != -1) continue;

이부분 예외처리였다. 벽으로 인해 지훈이가 가는길에 불이 도달 안했을 수 도 있기에 필요한 작업이였다.