[C++] 백준 5427:불

1. 문제

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

 

2. 문제 풀이

이 문제는 불이 매초마다 번질 때, 상근이가 몇 초만에 건물을 탈출 할 수 있는지 출력해야 한다. 불은 벽으로 번질 수 없으며 상근이는 벽을 통과하지 못한다. 상근이는 불이 옮겨진 칸이나 이제 불이 옮겨질 칸으로 이동할 수도 없다. 불이 상근이의 위치에 옮겨짐과 동시에 상근이가 다른 칸으로 이동할 수는 있다.

 

• 불도 매초마다 이동하고 상근이도 매초마다 이동할 수 있기 때문에 각각 BFS를 구현해야 한다. 그래서 상근이의 위치인 '@'이 입력으로 들어오는 경우와 불의 위치인 '*'이 입력으로 들어오는 경우, 각각의 큐에 push 한다. 
• 불이 먼저 이동한 후에, 상근이가 이동해야 한다.
• 불이 확산되는 BFS에서는 현재 fire 큐의 사이즈만큼만 반복해서 현재 확산할 수 있는 모든 경우의 수를 따져야 한다.
• 상근이의 이동도 같은 이유로 현재 큐의 사이즈만큼만 반복해야 한다.
• 배열 인덱스가 0보다 작거나 w, h보다 커지면 건물을 탈출한 것이므로 걸린 시간인 ans를 출력한다.

 

처음에 실수했던 부분은 moveFire와 bfs에서 큐가 없어질 때까지 반복해서 불의 탐색이 모두 끝나버리는 일이 발생했다. 

void moveFire() {
    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 && nx < w && ny >= 0 && ny < h) {
                if (graph[nx][ny] == '.'){
                    graph[nx][ny] = '*';
                    fire.push(pair<int, int> (nx, ny));
                }
                
            }
        }
    }
}

 

그래서 정답은 아래 코드와 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

vector<vector<char> > graph;
queue<pair<int, int> > q;
queue<pair<int, int> > fire;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int ans = 0;
int t, w, h;

void moveFire() {
    int fire_size = fire.size();
    for (int i = 0; i < fire_size; i++) {
        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 && nx < h && ny >= 0 && ny < w && (graph[nx][ny] == '.' || graph[nx][ny] == '@')) {
                graph[nx][ny] = '*';
                fire.push(pair<int, int> (nx, ny));
            }
        }
    }
}

int bfs() {
    int ans = 0;
    while (!q.empty()) {
        ans++;
        moveFire();

        int size = q.size();
        for (int j = 0; j < size; j++) {
            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 && nx < h && ny >= 0 && ny < w && graph[nx][ny] == '.') {
                    graph[nx][ny] = '@';
                    q.push(pair<int, int> (nx, ny));
                }
                else if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
                    return ans;
                }
            }
        }
    }

    return -1;
}

int main() {
    cin >> t;
    for (int k = 0; k < t; k++) {
        cin >> w >> h;
        graph.resize(h, vector<char>(w));

        // * '.': 빈 공간, '#': 벽, '@': 상근이의 시작 위치, '*': 불
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> graph[i][j];
                if (graph[i][j] == '@') {
                    q.push(pair<int, int> (i,j));
                }
                else if (graph[i][j] == '*') {
                    fire.push(pair<int, int> (i,j));
                }
            }
        }

        int ans = bfs();
        if (ans == -1) cout << "IMPOSSIBLE" << endl;
        else cout << ans << endl;

        while (!q.empty()) q.pop(); 
        while (!fire.empty()) fire.pop();
        graph.clear(); 
    }
    return 0;
}