이번 문제는 BFS를 통해 해결하였다. 처음에는 불의 이동을 브루트포스를 통해 구현하고, 상근이의 이동을 BFS로 구현하였다. 그러나 시간초과가 발생하였다. 불의 이동을 위해 불의 좌표를 모두 찾아야 하는 것에서 문제가 된 것으로 판단되었다. 그래서 불의 초기 좌표를 리스트로 저장하고, 불의 이동 시에 불이 없는 지역에 대하여 불을 한칸씩만 퍼트리고 불의 좌표를 새로 구성하였다(새로 만들어진 불의 좌표만으로 구성). 상근이의 이동 함수에서는 현재 좌표에서의 상근이의 이동시간과 전체 시간을 비교하여 전체 시간이 상근이의 이동시간보다 작거나 같을 경우에 불을 퍼트리고, 그 후에 상근이를 이동시켰다.

항상 문제를 똑바로 읽지 않아 사소한 부분에서 실수가 자주 발생하는 것 같다. 이번 문제에서도 불의 이동이 먼저 이뤄져야 하는데, 상근이의 이동을 먼저 수행시켜서 오답처리 당하였고, 이를 개선하여 해결하였다.

Code

import collections
t=int(input())
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
def fire_move():
    global fire
    new_fire=[]
    f=collections.deque(fire)
    while f:
        y, x=f.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<h and 0<=nx<w and grid[ny][nx]!='#' and grid[ny][nx]!='*':
                new_fire.append((ny, nx))
                grid[ny][nx]='*'
    fire=new_fire[:]
def sg_move(y, x):
    q=collections.deque()
    q.append((y, x, 0))
    visited=[[False for _ in range(w)] for _ in range(h)]
    time=0
    while q:
        y, x, cnt=q.popleft()
        if cnt>=time:
            fire_move()
            time+=1
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<h and 0<=nx<w and not visited[ny][nx] and grid[ny][nx]=='.':
                visited[ny][nx]=True
                q.append((ny, nx, cnt+1))
            elif not (0<=ny<h and 0<=nx<w):
                return cnt+1
    return 0
for _ in range(t):
    w, h=map(int, input().split())
    grid=[list(str(input())) for _ in range(h)]
    sg=[]
    fire=[]
    for i in range(h):
        for j in range(w):
            if grid[i][j]=='@':
                sg=[i, j]
            if grid[i][j]=='*':
                fire.append((i, j))
    answer=sg_move(sg[0], sg[1])
    if not answer:
        answer='IMPOSSIBLE'
    print(answer)