[백준] 5427번 불! ★

💡문제접근

• 평소에 풀었던 BFS 탐색 알고리즘과는 다른 문제였다. 일반적으로 풀었던 문제는 대개 한 번의 BFS 탐색을 수행하는 문제였는데 이 문제는 달랐다. 불이 번져나가는 탐색과 상근이가 빌딩에서 탈출하는 탐색 총 두 번의 과정을 수행해줘야한다.
• 큐가 비어있을때까지 수행했다가 무엇인가 잘못되었다는 점을 뒤늦게 인지했다. 큐가 비어있을때까지 한다면 하나의 탐색만이 계속 수행되기때문에 불이 제대로 번진건지 아니면 상근이가 탈출을 할 수 있는지가 확인되지않는다. 따라서 이 부분은 for문으로 대체하여 해결할 수 있었다.

💡코드(메모리 : 86132KB, 시간 : 2672ms)

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

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

def escape():
    flag = False
    for _ in range(len(start)):
        x, y = start.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                # 만약 이동하고자하는 좌표가 벽이 아니면서 불이 붙은 좌표가 아니고 빈 공간이라면?
                if not visited[nx][ny] and Building[nx][ny] == "." and Building[nx][ny] != "#" and Building[nx][ny] != "*":
                    flag = True
                    visited[nx][ny] = visited[x][y] + 1
                    start.append((nx, ny))
                # 만약 이동할 수 있는 위치가 없다면?
            else:
                return visited[x][y]
    # 만약 상근이의 현위치를 기준으로 전부 다 불이 붙어있다면?
    if not flag:
        return "IMPOSSIBLE"

T = int(input().strip())
for _ in range(T):
    w, h = map(int, input().strip().split())
    Building = []
    fire = deque()      # 불
    start = deque()     # 시작점
    for i in range(h):
        Building.append(list(input().strip()))
        for j in range(w):
            if Building[i][j] == "*":
                fire.append((i, j))
            elif Building[i][j] == "@":
                start.append((i, j))
    visited = [[0 for _ in range(w)] for _ in range(h)]
    # 상근이 현위치
    visited[start[0][0]][start[0][1]] = 1

    while True:
        burn()
        result = escape()
        if result:
            break
    print(result)

💡소요시간 : 1h 17m