(C++) 백준 4179번 - 불!

문제 링크 : https://www.acmicpc.net/problem/4179

4179번: 불!

풀이

BFS를 응용한 문제로, 불에 대한 BFS와 지훈이에 대한 BFS를 동시에 사용하는 방법으로 풀이하면 된다.

골드 4 문제답게 조건들을 설정하는 것이 매우 복잡했다.

#include <iostream>
#include <queue>
#include <utility>
#define X first
#define Y second

using namespace std;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
string brd[1002];
int fire_dist[1002][1002];
int jh_dist[1002][1002];
queue<pair<int,int> > Qj;
queue<pair<int,int> > Qf;
int r, c; // r = 행, c = 열

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

    cin >> r >> c;
    
    for(int i = 0; i < r; i++){ // 미로 저장
        string str;
        cin >> str;
        brd[i] = str;
        for(int j = 0; j < c; j++){
            if(brd[i][j] == 'F'){  // 불의 시작점 저장
                Qf.push({i,j});
                fire_dist[i][j] = 1;
            }
            if(brd[i][j] == 'J'){ // 지훈이의 시작점 저장
                Qj.push({i,j});
                jh_dist[i][j] = 1;
            }
        }
    }

    while(!Qf.empty()){ // 불이 붙는 시간 계산
        auto cur = Qf.front();
        Qf.pop();
        int prev = fire_dist[cur.X][cur.Y]; // 불이 붙은 시간
        for(int i = 0; i < 4; i++){
            int x = cur.X + dx[i];
            int y = cur.Y + dy[i];
            if(x >= 0 && x < r && y >= 0 && y < c){ // 유효성 검사
                // 다음 칸이 불이 붙을 수 있는 공간(.,J)이면
                if(brd[x][y] == 'J' or brd[x][y] == '.'){ 
                    if(fire_dist[x][y] == 0){ // 아직 불이 붙지 않았다면
                        Qf.push({x,y}); // 1분 후에 불이 붙을 장소를 큐에 저장
                        fire_dist[x][y] = prev + 1; // 1분 후 다음 칸에 불이 붙음을 저장
                    }else{ // 이미 불이 붙은 장소라면
                        if(fire_dist[x][y] > prev + 1){ // 더 빨리 불이 붙을 수 있는 장소였는지 체크 후
                            Qf.push({x,y}); // 재계산을 위해 큐에 저장
                            fire_dist[x][y] = prev + 1; // 1분 후 다음 칸에 불이 붙음을 저장
                        }
                    }
                }
            }
        }
    }

    while(!Qj.empty()){ // 지훈이가 도착하는 시간 계산
        auto cur = Qj.front();
        Qj.pop();
        if(cur.X == 0 or cur.X == r-1 or cur.Y == 0 or cur.Y == c-1){ // 지훈이의 시작점이 애초에 가장자리이면 바로 탈출
            cout << 1;
            return 0;
        }
        int prev = jh_dist[cur.X][cur.Y]; // 칸에 도착한 시간
        for(int i = 0; i < 4; i++){
            int x = cur.X + dx[i];
            int y = cur.Y + dy[i];
            if(x >= 0 && x < r && y >= 0 && y < c){ // 유효성 검사
                // 다음 칸이 지나갈 수 있는 공간(.)이면서 방문을 안 했으면서 불이 붙기 전에 도착할 수 있는 칸이거나 불이 붙이 않지 않았다면 도착할 수 있는 시간 계산
                if(brd[x][y] == '.' && (prev + 1 < fire_dist[x][y] or fire_dist[x][y] == 0) && jh_dist[x][y] == 0){
                    jh_dist[x][y] = prev + 1; // 1분 후 해당 칸에 도착할 수 있음을 저장
                    if(x == r-1 or y == c-1 or x == 0 or y == 0){ // 탈출 성공
                        cout << jh_dist[x][y]; // 다음 번에 탈출하는 것이지만 시작이 1이었으므로 그대로 출력
                        return 0;
                    }
                    Qj.push({x,y}); // 1분 후에 도착할 장소를 큐에 저장
                }
            }
        }
    }
    cout << "IMPOSSIBLE";
}