백준 4179번 C++

백준 4179번 불

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

4179번: 불!

정답 코드

#include <iostream>
#include<queue>
using namespace std;
#define X first
#define Y second
string board[1002];
int dist1[1002][1002];
int dist2[1002][1002]; 
int n, m;
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 >> n >> m;
    for (int i = 0; i < n; i++) {
        fill(dist1[i], dist1[i] + m, -1);
        fill(dist2[i], dist2[i] + m, -1);
    }
    for (int i = 0; i < n; i++)
        cin >> board[i];
    queue<pair<int, int> > Q1;
    queue<pair<int, int> > Q2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 'F') {
                Q1.push({ i,j });
                dist1[i][j] = 0;
            }
            if (board[i][j] == 'J') {
                Q2.push({ i,j });
                dist2[i][j] = 0;
            }
        }
    }

    while (!Q1.empty()) {
        auto 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 >= n || ny < 0 || ny >= m) continue;
            if (dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;
            dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
            Q1.push({ nx,ny });
        }
    }

  
    while (!Q2.empty()) {
        auto 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 >= n || ny < 0 || ny >= m) {
                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({ nx,ny });
        }
    }
    cout << "IMPOSSIBLE";
}

문제 풀이

bfs를 이용해서 풀었습니다. 일반적으로 bfs문제는 queue를 한 개 만들지만 두 개를 사용하였습니다.
Q1는 불이 움직이고 Q2는 지훈이가 이동한 큐입니다.
먼저 불이 확산할 수 있도록 Q1을 bfs로 돌립니다.
불에 따라서 지훈이의 움직임이 달라지기 때문에 Q1을 먼저 해야 합니다. 불이 확산되는데 걸리는 시간도 저장해줍니다. 그리고 나서 Q2를 bfs탐색합니다.
탈출하게 되면 그 배열값에 +1을 해주고 그게 아니라면 조건을 봐줘야 합니다. #은 벽이라서 continue해주고 dist2[nx][ny]가 0보다 크면 이미 지나간 곳이므로 continue해줍니다.
if (dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) 이 부분이 중요한데  
만약 배열값이 -1이 아니라면 불이 번지는 곳이고 뒤 조건은 시간인데  dist2가 더 크게 되면 이미 불이 번져서
지나갈 수 없다는 뜻입니다.