[백준 5427번/골드4] 불- 파이썬/bfs 복습필요

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

맞는 답

import sys
from collections import deque


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

def burn():
    for _ in range(len(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 graph[nx][ny] != "*" and graph[nx][ny] != "#":
                    graph[nx][ny] = "*"
                    fire.append((nx, ny))
    

def move():
    go = False
    for _ in range(len(human)):
        x, y = human.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx < h and 0 <= ny < w:
                if visited[nx][ny] == 0 and graph[nx][ny] == ".":
                    go = True
                    visited[nx][ny] = visited[x][y]+1
                    human.append((nx, ny))
            else:
                return visited[x][y]
    if not go:
        return "IMPOSSIBLE"
                    
                
if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        w, h = map(int, sys.stdin.readline().split())
        graph = [list(input().rstrip()) for _ in range(h)]
        fire = deque()
        human = deque()
        visited = [[0 for _ in range(w)] for _ in range(h)]
        for i in range(h):
            for j in range(w):
                if graph[i][j] == "*":
                    fire.append((i, j))
                elif graph[i][j] == "@":
                    human.append((i, j))
                    visited[i][j] = 1
        result = 0
        while (True):
            burn()
            result = move()
            if result:
                break
            
        print(result)

틀린 답

참고한 내용: https://2hs-rti.tistory.com/entry/%EB%B0%B1%EC%A4%80-5427%EB%B2%88-%EB%B6%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC

import sys
from collections import deque

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

def burn():
    for _ in range(len(fire_q)):
        x, y = fire_q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if graph[nx][ny] != "#" and graph[nx][ny] != "*":
                    graph[nx][ny] = "*"
                    fire_q.append((nx, ny))

def move():
    isgo = False
    for _ in range(len(human_q)):
        x, y = human_q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if not visited[nx][ny] and graph[nx][ny] != "#" and graph[nx][ny] != "*":
                    isgo = True
                    visited[nx][ny] = visited[x][y]+1
                    human_q.append((nx, ny))
                else:
                    return visited[x][y]
            if not isgo:
                return "IMPOSSIBLE"
    
if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        w, h = map(int, sys.stdin.readline().split())
        visited = [[0 for _ in range(w)] for _ in range(h)]
        human_q = deque()
        fire_q = deque()
        graph = [list(input().rstrip()) for _ in range(h)]
        
        for i in range(h):
            for j in range(w):
                if graph[i][j] == "*":
                    fire_q.append((i, j))
                if graph[i][j] == "@":
                    human_q.append((i, j))
                    visited[i][j] = 1
        
        result = 0
        while True:
            burn()
            result = move()
            if result:
                break
        
        print(result)