문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

---

풀이방법

• bfs 사용
• 불 먼저 이동 후 지훈이 이동
• 이동 시 deque 하나만 사용하면서 차례를 구분하기 위해 qSize를 활용하여 size만큼만 이동 후 나머지는 다음 차례에 이동
• 지훈이가 미로에서 벗어나면 탈출시간 출력 후 종료
• 지훈이가 미로에서 벗어나지 못하고 이동할 수도 없다면 IMPOSSIBLE 출력

Code

from collections import deque
R, C = map(int, input().split())

graph = []
fire = deque()
jihoon = deque()
for r in range(R):
    g = list(input())
    for c in range(C):
        if g[c] == 'J':
            jihoon.append((r, c))
            g[c] = '.'
        elif g[c] == 'F':
            fire.append((r, c))
    graph.append(g)
visited = [[False for _ in range(C)] for _ in range(R)]

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

def spread():
    fSize = len(fire)
    while fSize > 0:
        x, y = fire.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if graph[nx][ny] == '.':
                    graph[nx][ny] = 'F'
                    fire.append((nx, ny))
        fSize -= 1

t = 0
while jihoon:
    t += 1
    spread()
    jSize = len(jihoon)
    while jSize > 0:
        x, y = jihoon.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if graph[nx][ny] == '.' and not visited[nx][ny]:
                    jihoon.append((nx, ny))
                    visited[nx][ny] = True
            else:
                print(t)
                exit(0)
        jSize -= 1

print("IMPOSSIBLE")