[백준 - 5427] 불 - C++

분류: bfs, bfs 순차 실행 /

 

문제

테스트 케이스 1개인 같은 문제 풀이: [백준 - 4179] 불! - C++

문제 링크

문제 설명

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

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

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

입력

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

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

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

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

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

출력

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

 

풀이

- 불 BSF -> 시간 기록 -> 탈출 BFS

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

struct xy {int x, y; };
char board[1000][1001];
int times[1000][1001];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

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

    int T; cin >> T;
    while(T--) {
        int w, h;
        cin >> w >> h;
        queue<xy> Q;
        xy start;
        for(int i=0; i<h; i++) {
            cin >> board[i];
            for(int j=0; j<w; j++) {
                if(board[i][j] == '*') {
                    times[i][j] = 0;
                    Q.push({i, j});
                } else {
                    times[i][j] = -1;
                    if(board[i][j] == '@')
                        start = {i, j};
                }
            }
        }

        while(!Q.empty()) {
            xy cur = Q.front(); Q.pop();
            for(int d=4; d--;) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];
                if(nx<0 || nx>=h || ny<0 || ny>=w) continue;
                if(board[nx][ny] == '#') continue;
                if(times[nx][ny] != -1) continue;
                times[nx][ny] = times[cur.x][cur.y] + 1;
                Q.push({nx, ny});
            }
        }

        int ans = 0;
        times[start.x][start.y] = 0;
        Q.push(start);
        while(!Q.empty()) {
            int x = Q.front().x, y = Q.front().y; Q.pop();
            int nxt = times[x][y] + 1;
            if(x == 0 || x == h-1 || y == 0 || y == w-1) {
                ans = nxt;
                break;
            }
            for(int d=4; d--;) {
                int nx = x + dx[d], ny = y + dy[d];
                if(nx<0 || nx>=h || ny<0 || ny>=w) continue;
                if(board[nx][ny] == '#') continue;
                if(times[nx][ny] == -1 || nxt < times[nx][ny]) {
                    times[nx][ny] = nxt;
                    Q.push({nx, ny});
                }
            }
        }
        if(ans) cout << ans << '\n';
        else cout << "IMPOSSIBLE\n";
    }
}

 

 

- BFS 순차 실행

#include <iostream>
#include <queue>
using namespace std;
struct xy {int x, y; };
char board[1000][1001];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int w, h;

void spread(queue<xy> &F) {
    int size = F.size();
    while(size--) {
        xy cur = F.front(); F.pop();
        for(int d=4; d--;) {
            int nx = cur.x + dx[d];
            int ny = cur.y + dy[d];
            if(nx<0 || nx>=h || ny<0 || ny>=w) continue;
            if(board[nx][ny] == '#') continue;
            board[nx][ny] = '#';
            F.push({nx, ny});
        }
    }
}
bool escape(queue<xy> &S) {
    int size = S.size();
    while(size--) {
        int x = S.front().x, y = S.front().y;
        if(x == 0 || x == h-1 || y == 0 || y == w-1) return true;
        S.pop();
        for(int d=4; d--;) {
            int nx = x + dx[d], ny = y + dy[d];
            if(nx<0 || nx>=h || ny<0 || ny>=w) continue;
            if(board[nx][ny] == '#') continue;
            board[nx][ny] = '#';
            S.push({nx, ny});
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T;
    while(T--) {
        cin >> w >> h;
        queue<xy> S, F;
        for(int i=0; i<h; i++) {
            cin >> board[i];
            for(int j=0; j<w; j++) {
                if(board[i][j] == '*') {
                    board[i][j] = '#';
                    F.push({i, j});
                } 
                else if(board[i][j] == '@') {
                    board[i][j] = '#';
                    S.push({i, j});
                }
            }
        }
        int time = 0;
        while(!S.empty()) {
            time++;
            spread(F);
            if(escape(S)) break;
        }
        if(S.empty()) cout << "IMPOSSIBLE\n";
        else cout << time << '\n';
    }
}

풀이 설명은 

[백준 - 4179] 불! - C++ 에서