[BOJ] 5427. 불 (C++)

문제

건물의 일부에 불이 났고, 불은 매 초마다 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다.

상근이는 동서남북 인접한 칸으로 이동할 수 있으며 1초가 걸린다. 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다.

얼마나 빨리 빌딩을 탈출할 수 있는지 구하기. 탈출할 수 없는 경우 IMPOSSIBLE 출력

생각할 것

1초마다 인접한 방향으로 퍼져나가므로 BFS를 사용하자.

반례 1)

1
5 6
*#.##
#...#
#...#
#...#
#.@.#
#####

답 : 5

아래의 조건을 잘 정의해주어야 한다.

1. 벽이 아니고, 방문하지 않았고, 불이 없거나 불이 아직 퍼지기 전인 경우(도망칠 수 있는 경우)
2. if (board[nx][ny] != '#' && run[nx][ny] == -1 && (fire[nx][ny] == -1 || fire[nx][ny] > run[cx][cy] + 1))
3. 나는 불이 없는 경우에 대한 조건 처리를 잘못했었다..!

반례 2)

1
2 2
.@
..

답 : 1

1. 현재 위치가 모서리인 경우를 고려하지 않았다!

코드

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

using namespace std;

int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1};

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

    int T, w, h;
    cin >> T;

    while (T--) {
        cin >> w >> h;
        vector<vector<char>> board(h, vector<char>(w));
        vector<vector<int>> fire(h, vector<int>(w, -1));
        vector<vector<int>> run(h, vector<int>(w, -1));
        queue<pair<int, int>> q;
        pair<int, int> loc;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> board[i][j];
                if (board[i][j] == '@') loc = {i, j};
                else if (board[i][j] == '*') {
                    fire[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        // 초에 따른 불 이동
        while (!q.empty()) {
            int cx = q.front().first;
            int cy = q.front().second;
            q.pop();

            for (int k = 0; k < 4; k++) {
                int nx = cx + dx[k];
                int ny = cy + dy[k];
                if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if (board[nx][ny] != '#' && fire[nx][ny] == -1) { // 벽이 아니고, 아직 불이 없는 경우
                    fire[nx][ny] = fire[cx][cy] + 1;
                    q.push({nx, ny});
                }
            }
        }

        // 상근이 이동
        q.push(loc);
        run[loc.first][loc.second] = 0;
        bool escape = false;
        while (!q.empty()) {
            int cx = q.front().first;
            int cy = q.front().second;
            q.pop();

            if (cx == 0 || cx == h - 1 || cy == 0 || cy == w - 1) { // 현재 위치가 모서리일 경우 1초 뒤 탈출
                escape = true;
                cout << run[cx][cy] + 1 << "\\n";
                break;
            }

            for (int k = 0; k < 4; k++) {
                int nx = cx + dx[k];
                int ny = cy + dy[k];
                if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                // 벽이 아니고, 방문하지 않았고, 불이 없거나 불이 아직 퍼지기 전인 경우(도망칠 수 있는 경우)
                if (board[nx][ny] != '#' && run[nx][ny] == -1 &&
                    (fire[nx][ny] == -1 || fire[nx][ny] > run[cx][cy] + 1)) {
                    run[nx][ny] = run[cx][cy] + 1;
                    q.push({nx, ny});
                }
            }
        }
        if (!escape) cout << "IMPOSSIBLE" << "\\n";
    }

    return 0;
}