[BaekJoon] 백준 5427번 : 불

5427번 : 불

일반적인 BFS 문제이지만 불을 먼저 퍼지게 한 뒤 상근이를 이동시켜야한다.

---

import sys
from collections import deque


def fire():
    # 1. 배열과 방문여부, 이동방향 초기화한다.
    col, row = map(int, sys.stdin.readline().rsplit())
    maps = [list(sys.stdin.readline()) for _ in range(row)]
    dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    visit = [[False for _ in range(col)] for _ in range(row)]
    queue = deque([])

    # 2. 불의 위치와 상근이 위치를 저장한다.
    fires = []
    start = []
    for i in range(row):
        for j in range(col):
            if maps[i][j] == '@':
                start = [i, j, '@', 0]
            elif maps[i][j] == '*':
                fires.append([i, j, '*', 0])
    visit[start[0]][start[1]] = True

    # 3. 불이 먼저 퍼져야하기 때문에 큐에 불의 위치를 먼저 넣는다.
    for value in fires:
        queue.append(value)
        visit[value[0]][value[1]] = True
    queue.append(start)

    # 4. BFS를 시작한다.
    while queue:
        now_i, now_j, state, time = queue.popleft()
        # 5. 상근이가 맵 가장자리에 있는경우 탈출 할 수 있다.
        if state == '@' and (now_i == 0 or now_j == 0 or now_i == row - 1 or now_j == col - 1):
            return time + 1

        for value in dirs:
            visit_i, visit_j = now_i + value[0], now_j + value[1]
            if 0 <= visit_i < row and 0 <= visit_j < col and not visit[visit_i][visit_j]:
                # 6. 불인경우 퍼지면서 퍼지는 위치를 불로 바꿔준다.
                if maps[visit_i][visit_j] != '#' and state == '*':
                    maps[visit_i][visit_j] = '*'
                    visit[visit_i][visit_j] = True
                    queue.append([visit_i, visit_j, '*', time + 1])
                # 7. 상근이는 같은 시작 기준 이미 불이 퍼졌기 떄문에 이동만 하면 된다.
                elif maps[visit_i][visit_j] == '.' and state == '@':
                    visit[visit_i][visit_j] = True
                    queue.append([visit_i, visit_j, '@', time + 1])

    return "IMPOSSIBLE"


if __name__ == "__main__":
    for _ in range(int(input())):
        print(fire())