[🥇4 / 백준 5427 / 파이썬] 불

 

5427번: 불

 

문제

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

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

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

입력

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

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

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

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

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

출력

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

 

예제 입력 5 4 3 #### #*@. #### 7 6 ###.### #*#.#*# #.....# #.....# #..@..# ####### 7 4 ###.### #....*# #@....# .###### 5 5 ..... .***. .*@*. .***. ..... 3 3 ### #@# ###

예제 출력 2 5 IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE

 

풀이

 

불의 퍼짐과 상근이의 이동을 구분하여 시뮬레이션을 진행하는 BFS 문제이다.

한 틱에 불의 퍼짐과 상근이의 이동이 동시에 이루어진 후, 다음 틱을 진행한다.

상근이가 불이 붙으려는 자리에 이동할 수 없으므로, 불을 먼저 처리한 뒤 상근이의 이동을 진행한다.

 

처음엔 불과 상근이 두 개를 구분하여 BFS를 두 번 돌렸는데, 코드가 너무 길어져 큐에 들어온 원소의 타입별로 구분하여 BFS를 한 번만 진행하도록 리팩토링을 진행했다. 그리고 현재 기준 Python3에서 2012ms로 시간복잡도 3등을 기록했다!!

 

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

def solve():
    move = [(0,1),(1,0),(0,-1),(-1,0)]
    for _ in range(int(input())):
        w,h = map(int,input().split())
        board = [list(input()) for _ in range(h)]
        visited = [[False]*w for _ in range(h)]
        sk,fire = [],[]
        t = 0
        done = False

        for i in range(h):
            for j in range(w):
                if board[i][j] == "*":
                    fire.append(("*",i,j))
                elif board[i][j] == "@":
                    sk.append(("@",i,j))
                    board[i][j] = "."
        deq = deque(fire+sk)

        while deq:
            t+=1
            temp = []

            while deq:
                k,x,y = deq.popleft()
                for a,b in move:
                    dx=x+a; dy=y+b
                    if h>dx>=0 and w>dy>=0:
                        if not visited[dx][dy] and board[dx][dy] == ".":
                            temp.append((k,dx,dy))
                            visited[dx][dy] = True
                    else:
                        if k == "@":
                            print(t)
                            done = True
                            break
                if done:
                    break
            if done:
                break
            deq = deque(temp)
        else:
            print("IMPOSSIBLE")
solve()