이번 문제는 BFS 알고리즘을 활용하여 해결하였다. 여기서는 지훈이와 불이 동시에 움직이는 것을 표현해야 했기 때문에 이 부분에서 고민을 많이 했다. 처음에는 불의 모든 좌표를 리스트에 계속해서 모으고, 반복하며 지훈이를 한칸씩, 모든 불들을 상하좌우로 한칸씩 이동하도록 작성하였다. 모든 불들을 모두 순회해야 하기 때문에 시간 초과가 발생하였다.

그래서 다른 방법을 생각하던 중, 방문 처리를 하며 시간을 카운팅하고, 지훈이와 불의 방문 처리를 따로 진행하면 좋을 것 같다는 생각을 하였다. 지훈이와 불의 좌표를 deque에 담고, bfs함수 내에서 불의 이동을 먼저 BFS 방식으로 처리하여 불이 번지는 모든 좌표에 시간 카운팅을 하여 저장해주었다. 그리고 지훈이의 이동을 BFS 방식으로 처리하였다. 이때 지훈이가 이동하려는 좌표의 불 카운팅-1이 현재 지훈이의 카운팅보다 크거나, 불이 방문하지 않은 좌표일 경우에만 지훈이가 이동하도록 조건을 걸어주었다. 그리고 지훈이가 모서리에 도착할 경우, 현재 위치의 카운팅+1을 출력하도록 하였다.

• r, c를 입력받는다.
• 미로를 저장할 리스트 maze를 선언한다.
• 지훈이의 좌표를 담을 deque인 jq를 선언한다.
• 불의 좌표를 담을 deque인 fq를 선언한다.
• r번 반복하는 i에 대한 for문을 돌린다.
  -> maze를 입력받는다.
  -> maze[-1]의 길이만큼 반복하는 j에 대한 for문을 돌린다.
  --> 만약 maze[i][j]가 J일 경우,
  ---> jq에 (i, j)를 담는다.
  ---> maze[i][j]를 .으로 갱신한다.
  --> 만약 maze[i][j]가 F일 경우,
  ---> fq에 (i, j)를 담는다.
• 상하좌우에 대한 방향을 dy, dx에 짝지어 담는다.
• 지훈이의 방문 카운팅에 사용할 리스트 J를 r*c의 크기로 선언하고 False로 채운다.
• 불의 방문 카운팅에 사용할 리스트 F를 r*c의 크기로 선언하고 False로 채운다.
• J[jq[0][0]][jq[0][1]]을 0으로 갱신한다.
• fq의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  -> F[fq[i][0]][fq[i][1]]을 0으로 갱신한다.
• bfs함수를 선언한다.
  -> fq가 존재하는 동안 반복하는 while문을 돌린다.
  --> y, x를 fq에서 추출한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny를 y+dy[i]로 선언한다.
  ---> nx를 x+dx[i]로 선언한다.
  ---> 만약 ny가 0 이상, r 미만이고, nx가 0 이상, c 미만이고, F[ny][nx]가 False이고, maze[ny][nx]가 #이 아닐 경우,
  ----> F[ny][nx]를 F[y][x]+1로 갱신한다.
  ----> fq에 (ny, nx)를 넣는다.
  -> jq가 존재하는 동안 반복하는 while문을 돌린다.
  --> y, x를 jq에서 추출한다.
  --> 만약 y가 0이거나, y가 r-1이거나, x가 0이거나, x가 c-1일 경우,
  ---> J[y][x]+1을 출력한다.
  ---> 프로그램을 종료한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny를 y+dy[i]로 선언한다.
  ---> nx를 x+dx[i]로 선언한다.
  ---> 만약 ny가 0 이상, r 미만이고, nx가 0 이상, c 미만이고, J[ny][nx]가 False이고, maze[ny][nx]가 #이 아니고, F[ny][nx]-1이 J[y][x]보다 크거나 F[ny][nx]가 False일 경우,
  ----> J[ny][nx]를 J[y][x]+1로 갱신한다.
  ----> jq에 (ny, nx)를 넣는다.
• bfs()를 호출한다.
• IMPOSSIBLE을 출력한다.

Code

from collections import deque
import sys
input=sys.stdin.readline
r, c=map(int, input().split())
maze=[]
jq=deque()
fq=deque()
for i in range(r):
    maze.append(list(str(input())))
    for j in range(len(maze[-1])):
        if maze[i][j]=='J':
            jq.append((i, j))
            maze[i][j]='.'
        if maze[i][j]=='F':
            fq.append((i, j))
dy=[0, 0, -1, 1]
dx=[1, -1, 0, 0]
J=[[False]*c for _ in range(r)]
F=[[False]*c for _ in range(r)]
J[jq[0][0]][jq[0][1]]=0
for i in range(len(fq)):
    F[fq[i][0]][fq[i][1]]=0
def bfs():
    while fq:
        y, x=fq.popleft()
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<r and 0<=nx<c and not F[ny][nx] and maze[ny][nx]!='#':
                F[ny][nx]=F[y][x]+1
                fq.append((ny, nx))
    while jq:
        y, x=jq.popleft()
        if y==0 or y==r-1 or x==0 or x==c-1:
            print(J[y][x]+1)
            quit()
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<r and 0<=nx<c and not J[ny][nx] and maze[ny][nx]!='#' and (F[ny][nx]-1>J[y][x] or not F[ny][nx]):
                J[ny][nx]=J[y][x]+1
                jq.append((ny, nx))
bfs()
print('IMPOSSIBLE')