[백준][5427] 불

이 포스트는 백준 사이트의 불 문제 풀이입니다.

문제

해결 과정

이 문제는 불이 상하좌우 퍼지는 과정에서 상근이가 탈출할 수 있는지 확인하는 문제입니다.

여기서 불은 상하좌루로 동시에 퍼지기 떄문에 주어진 지형에서 퍼지는 과정을 BFS로 확인할 수 있습니다.
문제에서 최종적으로 구하고자 하는 것은 상근이가 탈출하는 시간이기 때문에
불이 옮겨지는 동시에 옮겨진 칸에 몇 초만에 도착했는지 기록한 뒤

상근이가 탈출할 수 있는 경로를 탐색할 때,
이미 불이 옮겨붙은 칸인지 판단할 수 있도록 사용하였습니다.

따라서 이 문제에서는 BFS 알고리즘을 2번 사용하여 문제의 결과를 확인할 수 있습니다.

코드 구현

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

using namespace std;

struct POINT {
    int row, col, time;
};
int dir_row[4]{-1, 1, 0, 0};
int dir_col[4]{0, 0, -1, 1};

int w, h;
queue<POINT> q_fire, q_player;
vector<vector<int>> fire_board;

void diffuse_fire() {
    while(false == q_fire.empty()) {
        auto curr = q_fire.front();
        q_fire.pop();

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.row + dir_row[dir];
            int new_col = curr.col + dir_col[dir];

            if(new_row < 0 || new_row >= h || new_col < 0 || new_col >= w)
                continue;
            if(-2 == fire_board[new_row][new_col] || 0 <= fire_board[new_row][new_col])
                continue;
            
            fire_board[new_row][new_col] = curr.time + 1;
            q_fire.push(POINT{new_row, new_col, curr.time + 1});
        }
    }
}

int get_player_moving_time() {
    if(q_player.front().row == 0 || q_player.front().row == h - 1
    || q_player.front().col == 0 || q_player.front().col == w - 1) {
        return 1;
    }

    vector<vector<bool>> visited(h, vector<bool>(w, false));
    visited[q_player.front().row][q_player.front().col] = true;

    while(false == q_player.empty()) {
        auto curr = q_player.front();
        q_player.pop();

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.row + dir_row[dir];
            int new_col = curr.col + dir_col[dir];

            if(new_row < 0 || new_row >= h || new_col < 0 || new_col >= w)
                continue;
            if(-2 == fire_board[new_row][new_col]
             || (0 <= fire_board[new_row][new_col] && fire_board[new_row][new_col] - 1 <= curr.time))
                continue;
            if(visited[new_row][new_col])
                continue;

            if(new_row == 0 || new_row == h - 1 || new_col == 0 || new_col == w - 1) {
                return curr.time + 2;
            }

            visited[new_row][new_col] = true;

            q_player.push(POINT{new_row, new_col, curr.time + 1});
        }
    }

    return 0;
}

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

    int T;
    char info;
    cin >> T;
    while(T--) {
        cin >> w >> h;
        fire_board.assign(h, vector<int>(w, -2));
        for(int row = 0; row < h; ++row) {
            for(int col = 0; col < w; ++col) {
                cin >> info;
                if(info == '#') {
                    fire_board[row][col] = 0;
                } else if(info == '.') {
                    fire_board[row][col] = -1;
                } else if(info == '*') {
                    q_fire.push({row, col, 0});
                } else if(info == '@') {
                    q_player.push({row, col, 0});
                }
            }
        }

        diffuse_fire();
        int time = get_player_moving_time();

        if(time == 0) {
            printf("IMPOSSIBLE\n");
        } else {
            printf("%d\n", time);
        }

        q_player = queue<POINT>();
        q_fire = queue<POINT>();
    }

    return 0;
}

실행 결과