[BOJ] 5427. 불

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

5427번: 불

4179번 불! (문제 링크) 문제와 스토리가 비슷한 문제인 것 같다.  (4179 불! 풀이 링크)

이 문제는 테스트 케이스가 최대 100개로 여러 개 있기 때문에 매번의 테스트 케이스에서 배열과, 큐 등 초기화를 잘해주어야 한다.

 

 

 

상근이가 최단 시간으로 탈출하는 경우와 불이 퍼지는 것을 구현하기 위해 BFS를 사용한다.

BFS는 상근이가 이동할 수 있는 곳이 더 없다면 끝나기 때문에 상근이의 좌표를 담은 큐가 비었다면 종료한다.

또는, 탈출에 성공한 경우에 바로 탐색을 종료한다.

 

 

 

큐 2개를 사용하여 상근이와 불의 위치를 각각의 큐에 넣어주고 각각 BFS를 진행한다. 같은 시간 동안 불을 먼저 이동시키고 상근이를 이동시키면 불이 확산되지 않은 곳으로 이동할 수 있다. 매 초마다 불을 먼저 확산시키고 다음에 상근이를 이동시키기 위해서 각자의 큐 사이즈만큼씩만 진행하면 된다. 한 번에 이동할 수 있는 위치만큼(현재 위치로부터 1만큼 이동한 곳)이 큐에 새로 들어가기 때문이다.

 

 

 

상근이가 빌딩 지도 범위를 넘어가면 탈출에 성공한 것이므로 바로 true를 리턴하여 시간을 출력해준다.

BFS가 끝났는데 빌딩을 탈출하지 못했다면 false를 리턴하고 문제 조건에 따라 IMPOSSIBLE을 출력한다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int h, w, time;
char map[1000][1000];
bool visit[1000][1000];
 
queue<pair<int, int> > sq; //상근이 이동 큐
queue<pair<int, int> > fq; //불 이동 큐
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
bool bfs() {
    time = 0;
 
    while (!sq.empty()) {
        int fqsize = fq.size();
        int sqsize = sq.size();
        int x, y, nx, ny;
 
        time++;
 
        //불 이동
        while (fqsize--) {
            x = fq.front().first;
            y = fq.front().second;
            fq.pop();
            for (int k = 0; k < 4; k++) {
                nx = x + dx[k];
                ny = y + dy[k];
                //범위 체크
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                //벽
                if (map[nx][ny] == '#') continue;
                //방문 체크
                if (visit[nx][ny]) continue;
 
                fq.push({ nx,ny });
                visit[nx][ny] = true;
            }
        }
 
        //상근이 이동
        while (sqsize--) {
            x = sq.front().first;
            y = sq.front().second;
            sq.pop();
            for (int k = 0; k < 4; k++) {
                nx = x + dx[k];
                ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
                    //탈출 성공
                    return true;
                }
                //벽
                if (map[nx][ny] == '#') continue;
                //방문 체크
                if (visit[nx][ny]) continue;
 
                sq.push({ nx,ny });
                visit[nx][ny] = true;
            }
        }
    }
 
 
 //탈출 실패
    return false;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
 
    while (T--) {        
        //다음 테스트 케이스를 위해 초기화
        memset(visit, false, sizeof(visit));
        while (!fq.empty()) fq.pop();
        while (!sq.empty()) sq.pop();
        bool exitFlag = false;
 
 
        cin >> w >> h;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> map[i][j];
                if (map[i][j] == '@') {
                    sq.push({ i,j });
                    map[i][j] = '.';
                    visit[i][j] = true;
                }
                else if (map[i][j] == '*') {
                    fq.push({ i,j });
                    visit[i][j] = true;
                }
            }
        }
 
 
        bool result = bfs();
 
        if (result) cout << time << '\n';
        else cout << "IMPOSSIBLE" << "\n";
    }
 
    return 0;
}