BOJ 4179. 불! (Python)

문제

BOJ 4179

내가 생각한 풀이

불의 이동 시간을 먼저 구한 후 지훈이의 이동 시간을 구한다.

 

2중 for문을 돌며 불이난 좌표와 지훈이의 좌표를 두 개의 큐에 나눠 담고 두 개의 dist에 0으로 초기화한다.

불 먼저 BFS를 돌며 dist_fire를 채움

 

지훈이 BFS를 돌며 dist_jihun을 채움

지훈이가 방문하지 않았으면서 빈 공간이면서 불이 나지 않았거나 불이 붙기 전에 갈 수 있는 곳에는 지훈이가 갈 수 있음.

nx, ny가 R, C 범위를 벗어났다면 dist_jihun[xp][yp] + 1을 출력하고 종료

아니라면 IMPOSSIBLE 출력

 

코드 (Python)

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

R, C = map(int, input().split())
graph = [list(input().strip()) for _ in range(R)]

queue_fire = deque([])
dist_fire = [[-1] * C for _ in range(R)]
queue_jihun = deque([])
dist_jihun = [[-1] * C for _ in range(R)]

direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(R):
    for j in range(C):
        if graph[i][j] == "F":
            queue_fire.append((i, j))
            dist_fire[i][j] = 0
        elif graph[i][j] == "J":
            queue_jihun.append((i, j))
            dist_jihun[i][j] = 0

while queue_fire:
    xp, yp = queue_fire.popleft()
    for dx, dy in direction:
        nx, ny = xp + dx, yp + dy
        if not (0 <= nx < R and 0 <= ny < C):
            continue
        if graph[nx][ny] != "#" and dist_fire[nx][ny] == -1:
            queue_fire.append((nx, ny))
            dist_fire[nx][ny] = dist_fire[xp][yp] + 1

while queue_jihun:
    xp, yp = queue_jihun.popleft()
    for dx, dy in direction:
        nx, ny = xp + dx, yp + dy
        if not (0 <= nx < R and 0 <= ny < C):
            print(dist_jihun[xp][yp] + 1)
            exit(0)
        if graph[nx][ny] == "." and dist_jihun[nx][ny] == -1 and (dist_fire[nx][ny] == -1 or dist_fire[nx][ny] > dist_jihun[xp][yp] + 1):
            queue_jihun.append((nx, ny))
            dist_jihun[nx][ny] = dist_jihun[xp][yp] + 1

print("IMPOSSIBLE")