이 문제는 불이 여러 곳에서 날 수 있다는 점과
불 -> 지훈 순으로 bfs를 수행해야 한다는 점을 캐치하면 쉽게 풀 수 있는 문제였습니다.
from collections import deque
r, c = map(int, input().split())
graph = [list(input()) for _ in range(r)]
def bfs():
global j
q = deque()
for x in range(r):
for y in range(c):
if graph[x][y] == 'J':
j = (x, y, 1)
elif graph[x][y] == 'F': # 불이 여러개일 수 있음
q.append((x, y, -1))
q.append(j) # F -> J 순으로 bfs
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while q:
x, y, cnt = q.popleft()
if cnt != -1 and (x in [0, r - 1] or y in [0, c - 1]):
print(cnt)
exit(0)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
if cnt == -1 and graph[nx][ny] not in ['#', 'F']:
q.append((nx, ny, -1))
graph[nx][ny] = 'F'
elif cnt > -1 and graph[nx][ny] == '.':
q.append((nx, ny, cnt + 1))
graph[nx][ny] = 'J'
bfs()
print("IMPOSSIBLE")
