[BOJ] 4179 - 불!

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

4179번: 불!

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int r, c;
int cnt = 0;
string board[1001];
int board_fire[1001][1001];
int board_path[1001][1001];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<int, int>> path;
queue<pair<int, int>> fire;

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

    cin >> r >> c;

    for(int i = 0; i < r; i++){
        cin >> board[i];
        fill(board_fire[i], board_fire[i] + c, -1);
        fill(board_path[i], board_path[i] + c, -1);
    }

    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(board[i][j] == 'J'){
                path.push(make_pair(i, j));
                board_path[i][j] = 0;
            }
                
            else if(board[i][j] == 'F'){
                fire.push(make_pair(i, j));
                board_fire[i][j] = 0;
            }
        }
    }

    while(!fire.empty()){
        int x = fire.front().first;
        int y = fire.front().second;
        fire.pop();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= r || ny < 0 || ny >= c){
                continue;
            }

            if(board_fire[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;

            board_fire[nx][ny] = board_fire[x][y] + 1;
            fire.push(make_pair(nx, ny));
        }
    }

    while(!path.empty()){
        int x = path.front().first;
        int y = path.front().second;
        path.pop();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= r || ny < 0 || ny >= c){
                cout << board_path[x][y] + 1;
                return 0;
            }

            if(board_path[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;

            if(board_fire[nx][ny] != -1 && board_fire[nx][ny] <= board_path[x][y] + 1){
                continue;
            }
            board_path[nx][ny] = board_path[x][y] + 1;
            path.push(make_pair(nx, ny));
            
        }
    }
    cout << "IMPOSSIBLE";
}

결과적으로 최단 경로를 구하는 문제이므로 BFS를 이용하지만 응용이 필요한 문제이다.

고려해야할 조건은 다음과 같다.

• 불이 있는 곳에는 지훈이가 갈 수 없다.
• 지훈이의 탈출 조건

 

if(board_fire[nx][ny] != -1 && board_fire[nx][ny] <= board_path[x][y] + 1){
	continue;
}

첫 번째 조건을 처리하기 위해서 불이 퍼지는 BFS를 먼저 실행한 후, 지훈이의 BFS를 실행하는데

지훈이가 해당 칸에 도착하는 시간이 해당 칸에 불이 퍼지는 시간과 같거나 작을 경우 갈 수 없다.

 

if(nx < 0 || nx >= r || ny < 0 || ny >= c){
	cout << board_path[x][y] + 1;
	return 0;
}

지훈이는 board의 가장자리에서 탈출가능하므로 이동하려는 칸의 좌표가 board의 크기를 벗어난다면

현재까지의 좌표 + 1을 출력하면서 종료하면 된다.

---

느낀점

두 가지 종류의 BFS를 각각 실행해주는 문제를 처음 접해서 신기했고 어려웠다.

BFS 자체는 굉장히 형식적이라 쉽다고 생각했는데 다양한 응용 BFS 문제를 풀어보아야겠다.