[C++/백준] 4179번: 불!*

문제 링크

4179번: 불!

풀이

BFS문제인데 접근 방식이 헷갈렸던 문제

불에 대한 BFS 탐색으로 모든 길에 대한 dist를 구하고, 지훈이는 그 dist를 토대로 BFS탐색을 해야한다.
또, 불은 2개 이상 있을 수 있어 거리에 대해 불이 올 최소 시간을 구해야 하는데, 이는 큐에 불 초기 위치를 바로바로 push해주면 된다. 나는 여기서 불 하나씩 탐색을 해서 헷갈렸음

코드

#include <iostream>
#include <queue>
#define INF 1000001
using namespace std;

char board[1001][1001];
int fireDist[1001][1001];
int dist[1001][1001];

int r, c;
int jy, jx;

int dy[4] = { -1, 0,1,0 };
int dx[4] = { 0,1,0,-1 };

void FireBFS(queue<pair<int, int>>& q)
{    
    while (!q.empty())
    {
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
            if (board[ny][nx] == '#' || fireDist[ny][nx] != INF) continue;
            fireDist[ny][nx] = fireDist[ty][tx] + 1;
            q.push({ ny,nx });
        }
    }
}

int BFS()
{
    queue < pair<int, int>> q;
    dist[jy][jx] = 0;
    q.push({ jy,jx });

    while (!q.empty())
    {
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if (ny < 0 || ny >= r || nx < 0 || nx >= c)
            {
                return dist[ty][tx] + 1;
            }
            if (board[ny][nx] == '#') continue;
            if (dist[ty][tx] + 1 >= fireDist[ny][nx]) continue;
            if (dist[ny][nx] != INF) continue;
            dist[ny][nx] = dist[ty][tx] + 1;
            q.push({ ny,nx });
        }
    }

    return -1;
}

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

    cin >> r >> c;

    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 'J')
            {
                jy = i;
                jx = j;
            }
            fireDist[i][j] = INF;
            dist[i][j] = INF;
        }
    }

    queue<pair<int, int>> q;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if (board[i][j] == 'F')
            {
                q.push({i,j});
                fireDist[i][j] = 0;
            }
        }
    }
    FireBFS(q);

    int answer = BFS();
    if (answer == -1) cout << "IMPOSSIBLE";
    else cout << answer;

}