[Python] Baekjoon - 4179. 불!

백준 4179번 불! 문제는 미로 속 지훈이가 불에 타기 전에 미로를 빠져나오는 최소 이동 횟수를 구하는 문제다. 최소 이동 횟수를 구하는 문제이므로 그래프 탐색 알고리즘 중 BFS를 이용해 해결할 수 있다. 난이도는 골드 4이다.

 

백준 4179번 불! 문제 정보

알고리즘 분류

- 그래프 탐색

난이도

- 골드 4

불! 문제 요약

벽과 빈칸으로 구성된 미로 속에 지훈이가 있는데, 미로 속 한 곳에 불이 붙었다. 지훈이가 불에 타기 전에 미로를 빠져나올 수 있다면 최소 이동 횟수를 구하는 문제다.

문제 풀이 과정

• 미로를 빠져나가기까지 최소 이동 횟수를 구해야 하므로 BFS를 이용한다.
• 지훈이가 한 칸 움직일 때마다 불도 상하좌우로 한 칸씩 번진다.
• 빈칸만 이동할 수 있는 지훈이가 미로를 빠져나가거나 더 이상 움직일 수 없을 때까지 이동한다.

코드

코드 설명

• fireList: 다음 차례 때 불이 번지기 시작하는 칸을 저장하는 리스트
• spreadFire(): 현재 미로에서 불이 한 칸씩 퍼지게 하는 함수(fireList 이용)
• escapeMaze(): BFS를 이용해 지훈이가 미로를 빠져나가기까지 걸리는 최소 이동 횟수를 구하는 함수

from collections import deque
import sys

dr, dc = [1,-1,0,0], [0,0,1,-1]


def spreadFire():
    global fireList, board
    tmp = []

    for fireR, fireC in fireList:

        for d in range(4):
            nextR, nextC = fireR + dr[d], fireC + dc[d]

            # 불이 번질 수 있는 칸이라면, 다음 차례때 이 칸에서부터 불이 다시 번질 수 있도록 저장
            if 0 <= nextR < R and 0 <= nextC < C and board[nextR][nextC] == '.':
                board[nextR][nextC] = 'F'
                tmp.append((nextR, nextC))

    fireList = tmp


def escapeMaze():
    global R, C, board, visited, start

    queue = deque()
    queue.append((start[0], start[1], 0))
    visited[start[0]][start[1]] = 1

    fireCnt = 0

    while len(queue) > 0:
        hereR, hereC, hereCnt = queue.popleft()

        if fireCnt != hereCnt:
            spreadFire()
            fireCnt += 1

        if board[hereR][hereC] == 'F':
            continue

        for d in range(4):
            nextR, nextC, nextCnt = hereR + dr[d], hereC + dc[d], hereCnt + 1

            if 0 <= nextR < R and 0 <= nextC < C:
                # 처음 방문했으며 방문 가능한 곳이라면 방문
                if visited[nextR][nextC] == 0 and board[nextR][nextC] == '.':
                    visited[nextR][nextC] = 1
                    queue.append((nextR, nextC, nextCnt))

            # 탈출 성공
            else:
                return nextCnt

    return "IMPOSSIBLE"


if __name__ == '__main__':
    R, C = map(int, input().split())
    board = []
    visited = [[0 for _ in range(C)] for _ in range(R)]
    fireList = []

    for r in range(R):
        tmp = [*sys.stdin.readline().strip()]
        for c in range(C):
            if tmp[c] == 'J':
                start = (r, c)
                tmp[c] = '.'
            elif tmp[c] == 'F':
                fireList.append((r, c))
        board.append(tmp)

    print(escapeMaze())