[BOJ] 5427번 : 불

문제 링크 : 백준 5427번

[문제 접근]

BFS를 이용해 구현하는 문제이다.
불의 경로를 나타내는 arr배열과 사람이 이동한 시간을 나타내는 check배열을 조건에 맞게 사용하면 된다.

1. 불
   • 불은 .과 @인 곳으로 옮겨붙을 수 있다.
2. 사람
   • 사람은 w,h에 대한 범위를 벗어나면 탈출에 성공
   • arr배열이 .이거나 check배열이 0이면 이동
   • bool타입 poss를 이용해 탈출에 성공했는지 아닌지 판단

1초마다 불과 사람이 움직이는 점을 이용해 전체 queue안에 불을 담당하는 queue와 사람을 담당하는 queue를 각각 담아 탐색했다.

⭐️ 불이 붙으려는 칸으로 이동할 수 없고 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있으므로 불을 먼저 옮긴 후 이동하면 된다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int t, w, h, sx, sy, fx, fy, ans=0;
char arr[1000][1000];
int check[1000][1000];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
queue<pair<int, int> > fire;
bool poss;

void BFS(int a, int b) {
    poss = true;
    queue<pair<int, int> > q;
    q.push(make_pair(a, b));

    while(!q.empty()) {
        // 불먼저 이동
        queue<pair<int, int> > temp;
        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 || ny<0 || nx>=h || ny>=w) continue;
                if(arr[nx][ny] == '.' || arr[nx][ny] == '@') {
                    arr[nx][ny] = '*';
                    temp.push(make_pair(nx, ny));
                }
            }
        }
        fire = temp;

        // 사람 이동
        queue<pair<int, int> > temp2;
        while(!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

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

                if(nx<0 || ny<0 || nx>=h || ny>=w) {
                    cout << check[x][y]+1 << "\n";
                    poss = false;
                    return;
                }

                if(arr[nx][ny] == '.' && check[nx][ny] == 0) {
                    check[nx][ny] = check[x][y] + 1;
                    temp2.push(make_pair(nx, ny));
                }
            }
        }
        q = temp2;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while(t--) {

        cin >> w >> h;
        while(!fire.empty()) fire.pop();
        memset(check, 0, sizeof(check));

        for(int i=0 ; i<h ; i++) {
            string s;
            cin >> s;
            for(int j=0 ; j<w ; j++) {
                arr[i][j] = s[j];
                if(arr[i][j] == '@') {
                    sx = i, sy = j;
                }
                if(arr[i][j] == '*') {
                    fire.push(make_pair(i, j));
                }
            }
        }
        BFS(sx, sy);
        if(poss) cout << "IMPOSSIBLE" << "\n";
    }
    
    return 0;
}