[Python/파이썬] 백준 5427번 불

5427번: 불

 

코드

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = int(1e9)

for _ in range(int(input())):
    w, h = map(int, input().split())
    board = []  # 빌딩 지도
    x, y = -1, -1   # 상근이 위치
    fire = []   # 불의 위치
    fire_board = [[INF]*w for _ in range(h)]    # 각 칸에 불 붙는데 걸리는 시간
    for i in range(h):
        row = list(input())
        for j in range(w):
            if row[j] == '@':   # 상근이의 초기 위치
                x = i
                y = j
            elif row[j] == '*':  # 초기 불들의 위치
                fire.append((i, j))
                fire_board[i][j] = 0
        board.append(row)
    # 칸마다 불이 붙는 시간 구하기
    q = deque(fire)
    while q:
        fx, fy = q.popleft()
        for d in range(4):
            nx = fx + dx[d]
            ny = fy + dy[d]
            if 0 <= nx < h and 0 <= ny < w and fire_board[nx][ny] > fire_board[fx][fy]+1 and board[nx][ny] == '.':
                q.append((nx, ny))
                fire_board[nx][ny] = fire_board[fx][fy]+1
    # 탈출 가능한지
    q = deque([(x, y, 0)])
    board[x][y] = '_'
    ans = -1
    while q:
        x, y, s = q.popleft()
        if x == 0 or x == h-1 or y == 0 or y == w-1:
            ans = s+1
            break
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < h and 0 <= ny < w and board[nx][ny] == '.' and fire_board[nx][ny] > s+1:
                q.append((nx, ny, s+1))
                board[nx][ny] = '_'
    print(ans if ans > 0 else "IMPOSSIBLE")

 

위의 코드는 두 개의 파트로 나눌 수 있다.

1. 칸마다 불이 붙는데 걸리는 시간 구하기
2. 상근이의 탈출 가능 여부 구하기

2개의 파트 모두 BFS를 사용했다.

 

첫번째, 칸마다 불이 붙는데 걸리는 시간을 구하기 위해서 처음에 빌딩의 지도를 입력받을 때 불의 위치를 fire 배열에 저장하고, 불이 붙는 시간을 표시할 2차원 배열 fire_board에 0이라고 표시해준다. 그리고 fire 배열에 있는 칸들을 deque에 넣고 BFS를 시작한다. 만약 옮겨가려는 칸 (nx, ny)로 갈 때, 현재 칸인 (fx, fy)에서 건너갈 때의 시간보다 fire_board[nx][ny]값이 더 크다면 fire_board[nx][ny]를 fire_board[fx][fy]+1로 갱신해주고 (nx, ny)를 deque에 넣어준다.

이 과정들을 반복하면 빌딩의 각 칸에 불이 번지는데 걸리는 시간을 구할 수 있다.

 

두번째, 상근이가 탈출 가능한지 알아보는 파트이다. 현재 위치를 시작점으로 BFS를 수행하면 된다. 만약 이동할 칸 (nx, ny)에 불 붙는 시간이 현재 칸 (x, y)에서 이동해서 가는 시간인 s+1보다 큰 경우에만 이동 가능하다. 이미 지나간 칸은 '_'으로 표시해준다.