백준 5427. 불

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

불! 이랑 똑같은 풀이 (상근이 먼저 이동 -> 불 이동)

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

t = int(input())
for tc in range(t):
    w, h = map(int,input().split())
    arr = [list(input().rstrip()) for _ in range(h)]
    q = deque()
    ans = 'IMPOSSIBLE'

    # 상근이 먼저 이동
    for i in range(h):
        for j in range(w):
            if arr[i][j] == '@':
                q.append((0,i,j))
                break

    # 불 퍼짐
    for i in range(h):
        for j in range(w):
            if arr[i][j] == '*':
                q.append((-1,i,j))

    while q:
        cnt, i, j = q.popleft()

        if cnt > -1 and arr[i][j] != '*' and (i == 0 or j == 0 or i == h - 1 or j == w - 1):
            ans = cnt + 1
            break

        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = i + dx, j + dy
            if 0 <= nx < h and 0 <= ny < w and arr[nx][ny] != '#':

                if cnt > -1 and arr[nx][ny] == '.':
                    q.append((cnt+1,nx,ny))
                    arr[nx][ny] = '@'
                elif cnt == -1 and arr[nx][ny] != '*':
                    q.append((-1,nx,ny))
                    arr[nx][ny] = '*'
    print(ans)

시간 3분의 1로 줄인 다른 풀이(불 이동->상근이 이동)

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

t = int(input())
for tc in range(t):
    w, h = map(int,input().split())
    arr = [list(input().rstrip()) for _ in range(h)]
    q = deque()
    fires = deque()

    for i in range(h):
        for j in range(w):
            if arr[i][j] == '@':
                q.append((0,i,j))
            elif arr[i][j] == '*':
                fires.append((i,j))

    def bfs(w, h, arr, q, fires):

        while q:
            for _ in range(len(fires)):
                f_i, f_j = fires.popleft()
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    nx, ny = f_i + dx, f_j + dy
                    if 0 <= nx < h and 0 <= ny < w and arr[nx][ny] == '.':
                        fires.append((nx, ny))
                        arr[nx][ny] = '*'

            for _ in range(len(q)):
                cnt, i, j = q.popleft()

                # 탈출 성공 1
                if i < 0 or i >= h or j < 0 or j >= w:
                    return cnt

                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    nx, ny = i + dx, j + dy
                    
                    # 다음에 탈출 성공 2
                    if nx < 0 or nx >= h or ny < 0 or ny >= w:
                        return cnt + 1

                    if arr[nx][ny] == '.':
                        q.append((cnt+1,nx,ny))
                        arr[nx][ny] = '@'
        return "IMPOSSIBLE"

    print(bfs(w, h, arr, q, fires))