[BOJ] C++ 4179 불! - 두 종류의 시작점을 포함한 최단경로, BFS

4179번: 불!

4 4
####
#JF#
#..#
#..#

ans : 3

---

전에 푼 토마토 문제와 비슷한 느낌이지만 굉장히 다르다. 불과 지훈이가 동시에 BFS를 돌리면 될 것 같지만 사실 무조건 불부터 돌려야 한다. 같은 시간대에 불이 도달할 수 있으면 지훈이는 해당 칸에 못 가기 때문이다. 동시에 돌리는 것처럼 큐 한 개로 처리하면 우선순위를 고려하기 굉장히 번거롭고 오래 걸린다. 따라서 불부터 BFS를 돌리고, 지훈이 도착시간이 불보다 작으면 방문 가능한 칸으로 BFS를 두 번 돌려야 한다.

 

지훈이의 BFS를 돌릴 때 방문가능한 칸인지 판단하는 부분에 아래의 문장이 들어간다.

if (dist[nx][ny] != -1 && dist[nx][ny] <= dist2[cur.first][cur.second] + 1)

여기서 dist[nx][ny] != -1이 굉장히 빠뜨리기 쉬운데, dist [nx][ny] == -1인 경우는 불이 해당칸을 도달하지 못하는 경우이므로 반드시 예외처리를 해줘야 한다.

if (nx < 0 || ny < 0 || nx >= n || ny >= m)
    {
        cout << dist2[cur.first][cur.second] + 1;
        return 0;
    }

또 위의 부분도 중요하다. cur 좌표의 상하좌우가 배열의 범위를 넘어간다면 cur 좌표가 가장자리에 있다는 것이므로 탈출에 성공했다는 것이다.

/** BFS 4179 불! **/
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#define MAX 1002
using namespace std;

string board[MAX];
int dist[MAX][MAX];
int dist2[MAX][MAX];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m; // n행 m열

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int, int>> Q;
    queue<pair<int, int>> Q2;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        fill(dist[i], dist[i] + m, -1);
        fill(dist2[i], dist2[i] + m, -1);
    }

    for (int i = 0; i < n; i++)
        cin >> board[i];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {

            if (board[i][j] == 'F')
            {
                Q.push(make_pair(i, j));
                dist[i][j] = 0;
            }
            if (board[i][j] == 'J')
            {
                Q2.push(make_pair(i, j));
                dist2[i][j] = 0;
            }
        }
    }

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

        for (int i = 0; i < 4; i++)
        {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            //(nx, ny)는 cur의 상하좌우 칸이다.
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if (dist[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            Q.push(make_pair(nx, ny));
        }
    }

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

        for (int i = 0; i < 4; i++)
        {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            //(nx, ny)는 cur의 상하좌우 칸이다.
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
            {
                cout << dist2[cur.first][cur.second] + 1;
                return 0;
            }
            if (dist2[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;
            if (dist[nx][ny] != -1 && dist[nx][ny] <= dist2[cur.first][cur.second] + 1)
                continue;
            dist2[nx][ny] = dist2[cur.first][cur.second] + 1;
            Q2.push(make_pair(nx, ny));
        }
    }

    cout << "IMPOSSIBLE";
}