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

---

1. 코드

import sys
from collections import deque

answer = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for _ in range(int(input())):
    flag = False
    m, n = map(int, sys.stdin.readline().rstrip().split())
    graph = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
    fire = []
    for i in range(n):
        for j in range(m):
            if graph[i][j] == '@':
                start = (i, j, 0)  # [3]=이동거리
            if graph[i][j] == '*':
                fire.append((i, j, 0))  # [3]=dummy
    q = deque(fire)
    q.append(start)
    while q:
        # 처음으로 탈출했다면 즉시 반복문 종료
        if flag:
            break

        x, y, cnt = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == '.':
                    char = graph[x][y]
                    graph[nx][ny] = char
                    if char == '*':
                        q.append((nx, ny, 0))  # dummy
                    elif char == '@':
                        q.append((nx, ny, cnt+1))  # cnt
            else:
                # 바로 탈출하지 않으면 cnt 값이 계속 갱신되어
                # cnt 가 최소한의 탈출 시간을 보장하지 않을 수 있다.
                if graph[x][y] == '@':
                    flag = True

    if flag:
        answer.append((cnt + 1))
    else:
        answer.append('IMPOSSIBLE')

for i in answer:
    print(i)

2. 후기

큐에서 꺼낼 때 반환값 형식을 맞추기 위해 더미값을 사용했다.

1. *일 경우 큐에 넣을 때, 더미값을 넣는다.
2. @일 경우에는 답으로 사용할 cnt 값을 1 증가시킨값을 큐에 넣는다.

• 활용했던 반례

2
2 2
@*
..
4 4
####
@..#
*#..
*###

탈출했다면 바로 while문을 종료시켜야 한다.
cnt 값이 계속 갱신되면 최소한의 탈출 시간을 보장할 수 없다.