[백준 / python] 5427: 불

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

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

풀이

import sys
from collections import deque

def escape():
    move = 0
    while players:
        move += 1
        total_count = len(players)
        for _ in range(total_count):
            i, j = players.popleft()
            if board[i][j] == "*":
                continue
            for dir_r, dir_c in dirs:
                new_r, new_c = i + dir_r, j + dir_c
                if not 0 <= new_r < h or not 0 <= new_c < w:
                    return move
                if board[new_r][new_c] == "#" or board[new_r][new_c] == "*":
                    continue
                if board[new_r][new_c] == "@":
                    continue
                board[new_r][new_c] = "@"
                players.append((new_r, new_c))
        spread_fire()
    return -1

def spread_fire():
    total_count = len(fires)
    for _ in range(total_count):
        i, j = fires.popleft()
        for dir_r, dir_c in dirs:
            new_r, new_c = i + dir_r, j + dir_c
            if not 0 <= new_r < h or not 0 <= new_c < w:
                continue
            if board[new_r][new_c] == "#" or board[new_r][new_c] == "*":
                continue
            board[new_r][new_c] = "*"
            fires.append((new_r, new_c))

dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
T = int(sys.stdin.readline())

for _ in range(T):
    w, h = map(int, sys.stdin.readline().split())
    board = [list(sys.stdin.readline().strip()) for _ in range(h)]
    players, fires = deque(), deque()
    for r in range(h):
        for c in range(w):
            if board[r][c] == '@':
                players.append((r, c))
            if board[r][c] == '*':
                fires.append((r, c))

    result = escape()
    if result == -1:
        print("IMPOSSIBLE")
    else:
        print(result)