BOJ - 5427 - 불

import sys
from collections import deque

def BFS(fire, person, W, H, maps, visit):
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    while person:
        temp = deque()
        while person:
            x, y = person.popleft()
            if maps[x][y] == "*":
                continue

            if x == 0 or x == H-1 or y == 0 or y == W-1:
                if maps[x][y] != "*": return maps[x][y]

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < H and 0 <= ny < W:
                    if maps[nx][ny] == "." and maps[nx][ny] != "*":
                        maps[nx][ny] = maps[x][y] + 1
                        temp.append((nx, ny))
        person = temp

        temp = deque()
        while fire:
            x, y = fire.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < H and 0 <= ny < W:
                    if visit[nx][ny] == False and maps[nx][ny] != "#":
                        maps[nx][ny] = "*"
                        visit[nx][ny] = True
                        temp.append((nx, ny))
        fire = temp
    return "IMPOSSIBLE"

def solution():
    T = int(input())
    for _ in range(T):
        maps = []
        fire = deque()
        person = deque()
        W, H = map(int, sys.stdin.readline().split())
        visit = [[False] * W for _ in range(H)]
        for _ in range(H):
            maps.append(list(str(sys.stdin.readline().strip())))

        for i in range(H):
            for j in range(W):
                if maps[i][j] == "@":
                    person.append((i, j))
                    maps[i][j] = 1
                elif maps[i][j] == "*":
                    fire.append((i, j))
                    visit[i][j] = True
        print(BFS(fire, person, W, H, maps, visit))

solution()

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