[골드 3] 백준 4179 - 불! (파이썬)

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

풀이

• 지훈이(J)는 미로에서 탈출해야 함.
• 불(F)은 매 분마다 상하좌우로 번짐.
• 지훈이는 1분에 1칸 이동 가능.
• 벽(#)은 지나갈 수 없음.
• 불이 도착한 시간보다 지훈이가 먼저 도착해야 탈출 가능.

fire[][] 와 jihun[][] 배열

• fire[i][j]: (i,j)에 불이 도달하는 시간
• jihun[i][j]: (i,j)에 지훈이가 도달하는 시간
• 1은 아직 도달하지 않은 상태

while q1:
    ...

• 먼저 모든 불의 위치에서 동시에 시작하여 BFS를 수행.
• (x, y) → (nx, ny)로 퍼져가며 fire[nx][ny] = fire[x][y] + 1로 시간 기록.

while q2:
    ...

• 지훈이가 이동할 수 있는 경로 탐색.
• 이동하려는 칸이 불이 이미 도착했거나 동시에 도착하면 안 됨

if fire[nx][ny] == -1 or fire[nx][ny] > jihun[nx][ny] + 1:

• 가장자리 도착 시 탈출 성공 → print(jihun[x][y] + 1) 후 종료.

코드

# 백준 4179 - 불!
# 분류 : BFS
# 문제집 - 0x09강 - BFS

from collections import deque
R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]

fire = [[-1] * C for _ in range(R)]
jihun = [[-1] * C for _ in range(R)]

q1 = deque()
q2 = deque()

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

for i in range(R) :
    for j in range(C) :
        if board[i][j] == 'F' :
            q1.append((i, j))
            fire[i][j] = 0
        elif board[i][j] == 'J' :
            q2.append((i, j))
            jihun[i][j] = 0

while q1 :
    x, y = q1.popleft()
    for d in range(4) :
        nx, ny = x + dx[d], y + dy[d]
        if 0 <= nx < R and 0 <= ny < C :
            if board[nx][ny] != '#' and fire[nx][ny] == -1:
                fire[nx][ny] = fire[x][y] + 1
                q1.append((nx, ny))

while q2 :
    x, y = q2.popleft()
    if x == 0 or x == R - 1 or y == 0 or y == C - 1 :
        print(jihun[x][y] + 1)
        exit()
    for d in range(4) :
        nx, ny = x + dx[d], y + dy[d]
        if 0 <= nx < R and 0 <= ny < C :
            if board[nx][ny] != '#' and jihun[nx][ny] == -1:
                if fire[nx][ny] == -1 or fire[nx][ny] > jihun[x][y] + 1:
                    jihun[nx][ny] = jihun[x][y] + 1
                    q2.append((nx, ny))

print("IMPOSSIBLE")