[백준 5427번] [BFS] 불

Approach

BFS를 2개 돌리면 된다. 시간 단위로 불과 상근이 모두 1칸씩 이동할 수 있으므로 상근이를 먼저 이동시키고 불을 이동시켜서 결과적으로 상근이가 경계선 밖을 넘는지 여부만 체크해주면 된다.

 

이미지로 가시화한 결과는 다음과 같다.

https://m.blog.naver.com/kks227/220785747864

너비 우선 탐색(Breadth-First Search) (수정 2018-11-22)

다만, 불의 경우에는 굳이 불인 경우에 대해서는 visited를 처리하지 않고 이동할 공간이 영역 내부이고 불에 해당하지 않으면 이동해주면 된다. 왜냐하면, 상근이가 먼저 이동하는 상황이므로 상근이가 방문하고 불이 번지는 경우에는 먼저 방문한 곳을 따로 처리해주어야 하기 때문이다. 

 

추가적으로, 상근이가 이동하고 불이 바로 번지는 경우가 존재하므로 예외처리해주어야 한다. 따라서 상근이가 이동하기 전에 불에 혹시 타지는 않았는지를 따로 체크해주어야 한다. 해당하는 대표적인 예시는 다음과 같다.

####

#@..

##*#

####

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;
int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
int r[1000][1000];
bool visited[1000][1000];

int main(void){
    int t;
    cin >> t;

    while(t--){
        memset(visited, 0, sizeof(visited));
        int n, m;
        cin >> m >> n;
        queue<pii> pos;
        queue<pii> fire_pos;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                char t;
                cin >> t;
                if(t == '.'){
                    r[i][j] = 1;
                }
                else if(t == '#'){
                    r[i][j] = 2;
                }
                else if(t == '@'){
                    r[i][j] = 3;
                    pos.push(make_pair(i, j));
                    visited[i][j] = 1;
                }
                else{
                    r[i][j] = 4;
                    fire_pos.push(make_pair(i, j));
                    visited[i][j] = 1;
                }
            }
        }

        int move = 1;
        int flag = false;
        int imp_flag = false;
        while(true){
            int human_q_size = pos.size();
            int fire_q_size = fire_pos.size();
            
            if(human_q_size == 0){
                imp_flag = true;
                break;
            }

            for(int i = 0; i < human_q_size; i++){
                int x = pos.front().first;
                int y = pos.front().second;
                pos.pop();
                if(r[x][y] != 3) continue;
                for(int j = 0; j < 4; j++){
                    int dx = x + move_x[j];
                    int dy = y + move_y[j];
                    if(dx < 0 || dx >= n || dy < 0 || dy >= m){
                        flag = true;
                        break;
                    }
                    else{
                        if(!visited[dx][dy] && r[dx][dy] == 1){
                            pos.push(make_pair(dx, dy));
                            visited[dx][dy] = 1;
                            r[dx][dy] = 3;
                        }
                    }
                }
            }
            if(flag == true || imp_flag == true) break;

            for(int i = 0; i < fire_q_size; i++){
                int x = fire_pos.front().first;
                int y = fire_pos.front().second;
                fire_pos.pop();
                for(int j = 0; j < 4; j++){
                    int dx = x + move_x[j];
                    int dy = y + move_y[j];
                    if(dx < 0 || dx >= n || dy < 0 || dy >= m) continue;
                    else{
                        if(r[dx][dy] == 1 || r[dx][dy] == 3){
                            fire_pos.push(make_pair(dx, dy));
                            visited[dx][dy] = 1;
                            r[dx][dy] = 4;
                        }
                    }
                }
            }
            move++;
        }
        if(imp_flag){
            cout << "IMPOSSIBLE\n";
        }
        else cout << move << "\n";
    }
    return 0;
}