5427: 불

• toc {:toc}

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• ’.’: 빈 공간
• ’#’: 벽
• ’@’: 상근이의 시작 위치
• ’*’: 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 “IMPOSSIBLE”을 출력한다.

출처: https://www.acmicpc.net/problem/5427

풀이

테스트 케이스를 여러 개로 사용하기 때문에 초기화를 진행해주는 것이 중요하다.

4179: 불!에서 풀었듯이 불의 BFS먼저 distance를 기록하고 불의 distance보다 상근이(1박2일 상근이가 생각나서 dog라 했다)의 distance가 더 작을 때 이동할 수 있도록 코딩했다.

4179: 불!에서는 테스트 케이스가 없어 return 0를 통해 아예 프로그램을 종료하면 됐지만 이 문제에서는 테스트 케이스를 이어나가야 했기 때문에 위 방식을 사용할 수 없었다.

⇒ 때문에 break를 사용했지만 break는 묶여있는 하나의 반복문만 중지시키기 때문에 이중 for문을 모두 중지시킬 수 없었고 이것이 틀리는 이유였다.

⇒ 이 문제는 그냥 중지시키지 않고 최솟값을 찾는 방법,

endflag를 이용하여 이중 for문을 탈출하는 방법을 이용해 해결하자.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define MX 10000000
 
char board[1002][1002];
int dog[1002][1002];
int fire[1002][1002];
int T, w, h;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
queue<pair<int, int>> Dq, Fq;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while(T--){
        cin >> w >> h;
        int ans = MX;
 
				// board와 fire, dog의 값을 초기화 해준다.
				// w, h범위 밖은 bfs 조건에서 거르기 때문에 초기화할 필요 없다.
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> board[i][j];
                if(board[i][j] == '*'){
                    fire[i][j] = 0;
                    dog[i][j] = -1;
                    Fq.push({i, j});
                }
                else if(board[i][j] == '@'){
                    dog[i][j] = 0;
                    fire[i][j] = -1;
                    Dq.push({i, j});
                }
                else{
                    dog[i][j] = -1;
                    fire[i][j] = -1;
                }
            }
        }
 
        // 불의 bfs
        while(!Fq.empty()){
            auto cur = Fq.front(); Fq.pop();
            for(int dir = 0; dir < 4; dir++){
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if(board[nx][ny] == '#' || fire[nx][ny] >= 0) continue;
                fire[nx][ny] = fire[cur.X][cur.Y] + 1;
                Fq.push({nx, ny});
            }
        }
/*
        for(int i = 0; i < h ; i++){
            for(int j = 0; j < w; j++){
                cout << fire[i][j] << '\t';
            }
            cout << endl;
        }
        cout << endl;
*/
        // 상근의 bfs
        int endflag = 0;
        while(!Dq.empty()){
            auto cur = Dq.front(); Dq.pop();
            for(int dir=0; dir < 4; dir++){
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(nx < 0 || nx >= h || ny < 0 || ny >= w){
                    // ans = min(ans, dog[cur.X][cur.Y]+1);
										// break대신 min으로 가장 빠른 탈출 가능 시간을 구한다.
                    ans = dog[cur.X][cur.Y]+1;
                    endflag=1;
                    break;
                }
                if(board[nx][ny] == '#' || dog[nx][ny] >= 0) continue;
                if(fire[nx][ny] != -1 && fire[nx][ny] <= dog[cur.X][cur.Y]+1) continue;
                dog[nx][ny] = dog[cur.X][cur.Y] + 1;
                Dq.push({nx, ny});
            }
            if(endflag) break;
        }
 
/*
        for(int i = 0; i < h ; i++){
            for(int j = 0; j < w; j++){
                cout << dog[i][j] << '\t';
            }
            cout << endl;
        }
*/
 
        if(ans != MX)
            cout << ans << endl;
        else
            cout << "IMPOSSIBLE" << endl;
 
        while(!Dq.empty()){
            Dq.pop();
        }
    }
}