핵심 아이디어:
1) 불을 먼저 BFS로 확산시키면서 새로운 2차원 리스트에 맵 좌표마다 불이 도착할 시간을 기록
2) 지훈이를 BFS 진행하면서 이동 조건에time + 1 < fire_time[nx][ny]을 넣어서 불이 도착하는 시간보다 지훈이가 먼저 도착할 수 있다면 이동하게 함
import sys
from collections import deque
input = sys.stdin.readline
r, c = map(int, input().split())
maps = []
fire_time = [[float('inf')] * c for _ in range(r)] # 무한대로 초기화해야 초기 불이 없는 경우도 커버 가능
j_time = [[-1] * c for _ in range(r)]
fire_list = [] # 초기 불이 1개 이상 존재할 수 있음에 주의
j_x, j_y = 0, 0
for i in range(r):
line = list(input().rstrip())
for j in range(c):
if line[j] == 'J':
j_x, j_y = i, j
if line[j] == 'F':
fire_list.append((i, j))
maps.append(line)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(j_x, j_y, maps):
visited = set()
q = deque()
# 초기 불 좌표들을 모두 큐에 넣기
for x, y in fire_list:
q.append((x, y, 0))
visited.add((x, y))
fire_time[x][y] = 0
# 불 BFS하며 fire_time에 해당 칸에 불이 도착하는 시간 기록 ----------------
while q:
x, y, time = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < r and 0 <= ny < c and maps[nx][ny] != '#' and (nx, ny) not in visited:
q.append((nx, ny, time + 1))
fire_time[nx][ny] = time + 1
visited.add((nx, ny))
# fire_time을 확인하며 지훈이 BFS -----------------
visited = set()
q.append((j_x, j_y, 0))
visited.add((j_x, j_y))
j_time[j_x][j_y] = 0
while q:
x, y, time = q.popleft()
# 현재 위치가 맵의 테두리라면 탈출
if (x == 0 or x == r - 1) or (y == 0 or y == c - 1):
print(time + 1) # 마지막에 밖으로 한칸 더 이동해야 탈출이므로 + 1 해주기
break
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 해당 칸에 불이 도착하는 시간보다 지훈이가 도착하는 시간이 더 빠를 경우만 이동 가능
if 0 <= nx < r and 0 <= ny < c and maps[nx][ny] != '#' and (nx, ny) not in visited and time + 1 < fire_time[nx][ny]:
q.append((nx, ny, time + 1))
j_time[nx][ny] = time + 1
visited.add((nx, ny))
# 찾지 못했다면 불가능
else:
print('IMPOSSIBLE')
bfs(j_x, j_y, maps)
