[Gold IV] 불! - 4179

문제 링크

성능 요약

메모리: 71604 KB, 시간: 1544 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 2월 1일 00:16:04

문제 설명

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

#: 벽
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

풀이

from collections import deque
import sys
input = sys.stdin.readline
r, c = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(r)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
jihoon = deque()
fire = deque()
f_time = [[0]*c for _ in range(r)]
j_time = [[0]*c for _ in range(r)]
for i in range(r):
    for j in range(c):
        if graph[i][j] == "J":
            jihoon.append([i, j])
            j_time[i][j] = 1
        if graph[i][j] == "F":
            fire.append([i, j])
            f_time[i][j] = 1

    
        
          
def bfs():
    while fire:
        x, y = fire.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
            if graph[nx][ny] != "#" and not f_time[nx][ny]:
                f_time[nx][ny] = f_time[x][y] + 1
                fire.append([nx, ny])
  
    while jihoon:
        x, y = jihoon.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                return j_time[x][y]
            if graph[nx][ny] == "#" or j_time[nx][ny]:
                continue
            if not f_time[nx][ny] or f_time[nx][ny] > j_time[x][y] + 1:
                j_time[nx][ny] = j_time[x][y] + 1
                jihoon.append([nx, ny])
    return "IMPOSSIBLE"

print(bfs())

그래프에서 `J`인 것은 따로 큐에 담고, `F`인 것도 따로 큐에 담는다. 담으면서 시간도 초기화한다.

bfs를 돌면서 먼저 불이 번지는 시간을 구하고 지훈이가 도망갈 수 있는 시간 또한 bfs로 구한다.

다만 지훈이는 이동할 칸에 불이 붙지 않았거나 불이 붙었더라도 지훈이가 이동한 시간보다 1이 더 크면 이동할 수 있다.

그 이외는 `IMPOSSIBLE`을 반환하면 된다.