BOJ 5427 - 불 링크
(2023.09.19 기준 G4)

문제

상근이가 빈 공간과 벽으로 이루어진 건물에 갇혀 있고, 일부에는 불이 났다.
불은 매 초마다, 인접한 빈 공간으로 퍼져나가며 벽에는 불이 붙지 않는다. 상근이는 매 초마다, 인접한 빈 공간으로 이동할 수 있으며, 불이 옮겨진 칸이나 이제 옮겨질 예정인 칸으로는 가지 못한다.

상근이가 건물 밖으로 탈출하는 최소 시간 출력

알고리즘

BFS

풀이

두번째 테스트 케이스를 그림으로 나타내면 위와 같다.

상근이는 불이 있는 곳으로 가지 못한다. 그리고 불은 상근이와 같은 속도로 인접한 곳으로 옮겨 붙는다.
결국, 상근이는 갈 수 있는 곳이 시간에 따라 달라진다.

일단은 불에 대해서 BFS를 돌려보자.

돌리면 위와 같이 결과가 나온다.

그럼 이제 상근이에 대해 BFS를 할 차례이다.
만약에 현재 지점에서 인접한 다음 지점으로 갈 때, 이미 불이 붙어 있었다면? 즉, 불이 먼저 도착했다면? 가지 못한다.

마찬가지로 불과 같이 도착한다면? 즉, 불과 같은 거리에 있는 곳으로 가려고 한다면? 불가능하다. 왜냐 하면, 지문에서 '이제 불이 옮겨질 예정인 곳으로도 가지 못한다'고 명시되어 있기 때문이다.

위 두 경우를 합치면 결국은 인접한 다음 지점의 도착 예정 시간이 불의 도착 시간보다 더 일찍이어야 한다. 이에 따라 BFS를 돌리면

이렇게 과정이 나온다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1000;
const pii dir[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

string matrix[MAXN];
deque<pii> dq, dq_fire;
int dist[MAXN][MAXN], dist_fire[MAXN][MAXN];

void solve(){
    int w, h; cin >> w >> h;
    for (int i = 0; i < h; i++) cin >> matrix[i];

    // 불이 각 지점마다 도착하는 시간을 계산해야 한다.
    // 불의 첫 위치를 dq_fire에 담자.
    // 추가로 상근이의 위치도 dq에 담자.
    dq.clear(); // 상근이의 위치를 담은 dq는 도중에 종료되어 요소가 남아 있을 수 있다.
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
        dist[i][j] = dist_fire[i][j] = -1; // -1은 아직 방문 전
        if (matrix[i][j] == '*'){
            dq_fire.push_back({i, j});
            dist_fire[i][j] = 0;
        }
        else if (matrix[i][j] == '@'){
            dq.push_back({i, j});
            dist[i][j] = 0;
        }
    }

    // 불에 대해서 BFS
    while (!dq_fire.empty()){
        auto [i, j] = dq_fire.front(); dq_fire.pop_front();
        for (auto [di, dj]: dir)
            if (0 <= i + di && i + di < h && 0 <= j + dj && j + dj < w && matrix[i + di][j + dj] != '#' && !~dist_fire[i + di][j + dj]){
                dq_fire.push_back({i + di, j + dj});
                dist_fire[i + di][j + dj] = dist_fire[i][j] + 1;
            }
    }

    // 상근이에 대해서 BFS
    // 이제 불이 붙으려는 칸에도 가지 못하므로
    // 가려는 칸의 불이 도착하는 시간보다 더 빨리 가야 한다.
    while (!dq.empty()){
        auto [i, j] = dq.front(); dq.pop_front();
        for (auto [di, dj]: dir){
            if (!(0 <= i + di && i + di < h && 0 <= j + dj && j + dj < w)){ // 다음 위치가 범위를 벗어난다면 탈출 성공
                cout << dist[i][j] + 1 << '\n';
                return;
            }
            if (matrix[i + di][j + dj] != '#' && !~dist[i + di][j + dj] && (!~dist_fire[i + di][j + dj] || dist_fire[i + di][j + dj] > dist[i][j] + 1)){
                dq.push_back({i + di, j + dj});
                dist[i + di][j + dj] = dist[i][j] + 1;
            }
        }
    }

    // BFS를 더 이상 진행하지 못한다면 탈출 실패
    cout << "IMPOSSIBLE\n";
}

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

    int T; cin >> T;
    while (T--) solve();
}

• Python

import sys; input = sys.stdin.readline
from collections import deque

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def solve():
    w, h = map(int, input().split())
    matrix = [input().strip() for _ in range(h)]

    # 불이 각 지점마다 도착하는 시간을 계산해야 한다.
    # 불의 첫 위치를 dq_fire에 담자.
    # 추가로 상근이의 위치도 dq에 담자.
    dq_fire = deque(); dq = deque()
    dist_fire = [[-1] * w for _ in range(h)] # -1은 아직 방문 전
    dist = [[-1] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == '*':
                dq_fire.append((i, j))
                dist_fire[i][j] = 0
            elif matrix[i][j] == '@':
                dq.append((i, j))
                dist[i][j] = 0

    # 불에 대해서 BFS
    while dq_fire:
        i, j = dq_fire.popleft()
        for di, dj in dir:
            if 0 <= i + di < h and 0 <= j + dj < w and matrix[i + di][j + dj] != '#' and not ~dist_fire[i + di][j + dj]:
                dq_fire.append((i + di, j + dj))
                dist_fire[i + di][j + dj] = dist_fire[i][j] + 1

    # 상근이에 대해서 BFS
    # 이제 불이 붙으려는 칸에도 가지 못하므로
    # 가려는 칸의 불이 도착하는 시간보다 더 빨리 가야 한다.
    while dq:
        i, j = dq.popleft()
        for di, dj in dir:
            if not ( 0 <= i + di < h and 0 <= j + dj < w): # 다음 위치가 범위를 벗어난다면 탈출 성공
                print(dist[i][j] + 1)
                return
            if matrix[i + di][j + dj] != '#' and not ~dist[i + di][j + dj] and (not ~dist_fire[i + di][j + dj] or dist_fire[i + di][j + dj] > dist[i][j] + 1):
                dq.append((i + di, j + dj))
                dist[i + di][j + dj] = dist[i][j] + 1

    # BFS를 더 이상 진행하지 못한다면 탈출 실패
    print('IMPOSSIBLE')

for _ in range(int(input())):
    solve()