문제

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

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

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

입력

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

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

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

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

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

출력

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

---

문제풀이

• bfs 사용
• 불 먼저 이동 후 상근이 이동
• 이동 시 deque 하나만 사용하면서 차례를 구분하기 위해 qSize를 활용하여 size만큼만 이동 후 나머지는 다음 차례에 이동
• 상근이가 미로에서 벗어나면 탈출시간 출력 후 종료
• 상근이가 미로에서 벗어나지 못하고 이동할 수도 없다면 IMPOSSIBLE 출력

Code

from collections import deque
import sys

input = sys.stdin.readline

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

def init():
    global R, C
    global graph, fire, position, visited

    C, R = map(int, input().split())

    graph = []
    fire = deque()
    position = deque()
    for r in range(R):
        g = list(input())
        for c in range(C):
            if g[c] == '@':
                position.append((r, c))
                g[c] = '.'
            elif g[c] == '*':
                fire.append((r, c))
        graph.append(g)
    visited = [[False for _ in range(C)] for _ in range(R)]

def spread():
    fSize = len(fire)
    while fSize > 0:
        x, y = fire.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if graph[nx][ny] == '.':
                    graph[nx][ny] = '*'
                    fire.append((nx, ny))
        fSize -= 1

def solution():
    t = 0
    while position:
        t += 1
        spread()
        pSize = len(position)
        while pSize > 0:
            x, y = position.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < R and 0 <= ny < C:
                    if graph[nx][ny] == '.' and not visited[nx][ny]:
                        position.append((nx, ny))
                        visited[nx][ny] = True
                else:
                    print(t)
                    return
            pSize -= 1
    print("IMPOSSIBLE")

def main():
    T = int(input())
    for _ in range(T):
        init()
        solution()

main()