백준 5427번 불

import sys
from collections import deque

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

T = int(input())

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

for _ in range(T):
    w, h = map(int, input().split())
    graph = []
    queue = deque()

    for _ in range(h):
        graph.append(list(input().strip()))

    visited = [[0] * (w) for _ in range(h)]


    def bfs():

        while queue:
            y, x = queue.popleft()

            if y == 0 or x == 0 or y == h-1 or x == w-1:
                print(visited[y][x])
                return

            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]

                if 0 <= ny < h and 0 <= nx < w:
                    if graph[ny][nx] == '.' and visited[ny][nx] == 0:

                        for f in range(4):
                            fy = ny + dy[f]
                            fx = nx + dx[f]

                            if 0 <= fy < h and 0 <= fx < w:
                                if graph[fy][fx] == '*':
                                    continue

                                visited[ny][nx] = visited[y][x] + 1
                                queue.append([ny, nx])

        print('IMPOSSIBLE')
        return

    """ for column in range(h):
        for row in range(w):
            if graph[column][row] == '*':
                for i in range(4):
                    ny = column + dy[i]
                    nx = row + dx[i]

                    if 0 <= ny < h and 0 <= nx < w:
                        graph[ny][nx] = '*' """

    for y in range(h):
        for x in range(w):
            if graph[y][x] == '@':
                queue.append([y, x])
                visited[y][x] = 1
                bfs()

불 처리하는게 시간내에 되지 않았다. 정답코드는 어떻게 했는지 확인해보자..

from collections import deque
import sys
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
    global q, f
    while q: # 사람이 먼저 이동하고 탈출하면 끝나기 때문에 사람의 이동 경로를 기록한 que를 선언한다.
        temp = deque()
        while q: # 사람 이동 큐
            x, y = q.popleft()
            if (x == h - 1 or y == w - 1 or x == 0 or y == 0) and s[x][y] != "*": return s[x][y]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "." and s[x][y] != "*":
                    s[nx][ny] = s[x][y] + 1
                    temp.append([nx, ny])
        q = temp
        temp = deque()
        while f: # 불 이동 큐
            x, y = f.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < h and 0 <= ny < w and visit[nx][ny] == 0 and s[nx][ny] != "#":
                    s[nx][ny] = "*"
                    visit[nx][ny] = 1
                    temp.append([nx, ny])
        f = temp
t = int(input())
for i in range(t):
    w, h = map(int, input().split())
    s, f, q = [], deque(), deque() # s는 입력 배열, 큐 2개
    visit = [[0] * w for i in range(h)]
    for j in range(h):
        a = list(input().strip())
        s.append(a)
        for k in range(w):
            if a[k] == "@":
                s[j][k] = 0
                q.append([j, k])
            elif a[k] == "*":
                f.append([j, k])
                visit[j][k] = 1
    result = bfs()
    print(result + 1 if result != None else "IMPOSSIBLE")

문제를 잘 못 이해하고 있는 것을 확인했다. 불이 동서남북으로 한번만 번져나가는 줄 알고 어떻게 구현해야하나 고민을 했는데 시간이 지날 수록 불이 번져나간다는 이야기였다. 그럴경우 사람과 불을 차례로 이동시켜주면 되는 bfs문제였다. 결국 큐를 2개 만들어서 bfs를 2번 해주면 되는 문제였다.