[Python] 백준 5427번: 불

f와 s의 bfs를 분리하는 코드가 많았는데,
저는 f -> s 순으로 큐에 삽입하여 한번에 bfs를 돌았습니다.

방문체크는 f는 *로, s는 @로 표시했고,
(nx, ny)의 값이 . 혹은 @이면 불이 번지도록 했습니다.

최단 경로, 최단 시간을 bfs로 구하기 위해서는 bfs의 단계 수를 카운트해주는 변수가 필요합니다.

보통 visited[x][y]에 bfs의 단계 수를 기록하거나, q에 bfs의 단계 수를 함께 삽입합니다. 저는 입력받은 배열을 바로 visited 배열로 사용했기 때문에, 후자의 방법을 이용해서 단계 수를 카운트해주었습니다.

코드는 아래와 같습니다.

from collections import deque

def bfs(s, F, w, h, board):
    q = deque()
    # f -> s 순으로 bfs
    for f in F:
        q.append((f[0], f[1], -1))
    q.append((s[0], s[1], 0))

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

    while q:
    	# f의 bfs면 cnt=-1, s의 bfs면 cnt=시간
        x, y, cnt = q.popleft()

        if cnt != -1 and (x in [0, h - 1] or y in [0, w - 1]):
            return cnt + 1	# 탈출

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if cnt == -1 and board[nx][ny] in ['.', '@']:
                    q.append((nx, ny, -1))
                    board[nx][ny] = '*'
                elif cnt > -1 and board[nx][ny] == '.':
                    q.append((nx, ny, cnt + 1))
                    board[nx][ny] = '@'
    return 'IMPOSSIBLE'

t = int(input())

for _ in range(t):
    w, h = map(int, input().split())
    board = [list(input()) for _ in range(h)]
    s = (0, 0)
    f = []	# 여러 곳에서 불이 날 수 있음

    for i in range(h):
        for j in range(w):
            if board[i][j] == '@':
                s = (i, j)
            elif board[i][j] == '*':
                f.append((i, j))
                
    print(bfs(s, f, w, h, board))