[백준] 5427번 - 불 (파이썬)

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

# 불
from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def burn():
    for _ in range(len(fire)):
        x, y = fire.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] != '#' and arr[nx][ny] != '*':
                    arr[nx][ny] = '*'
                    fire.append((nx, ny))


def move():
    isgo = False
    for _ in range(len(start)):
        x, y = start.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 0 and arr[nx][ny] != '#' and arr[nx][ny] != '*':
                    isgo = True
                    visited[nx][ny] = visited[x][y] + 1
                    start.append((nx, ny))
            else:
                return visited[x][y]
    if not isgo:
        return 'IMPOSSIBLE'


T = int(input())
for _ in range(T):
    M, N = map(int, input().split())
    arr = []
    fire = deque()
    start = deque()
    for i in range(N):
        arr.append(list(input().strip()))
        for j in range(M):
            if arr[i][j] == '*':
                fire.append((i, j))
            if arr[i][j] == '@':
                start.append((i, j))
    visited = [[0] * M for _ in range(N)]
    visited[start[0][0]][start[0][1]] = 1

    result = 0
    while True:
        burn()
        result = move()
        if result:
            break

    print(result)

 

BFS

1. 불길의 시작 위치와 출발위치를 각각 fire리스트와 start리스트에 append

2. result값이 return될 때까지 반복

    - burn (불길이 번지는 함수) : 현재 불이 있는 위치의 상하좌우에 불이 번짐

    - move (상근이가 이동하는 함수) : 현재 상근이가 있는 위치의 상하좌우로 이동

       - 만약 범위 밖으로 이동한다면 return 이동시간

       - 만약 이동이 없다면 return 'IMPOSSIBLE'

3. result 출력