문제 4179

풀이

나의 경우, 불과 지훈을 큐 하나로 하다가 꼬여서 풀지 못함.

지훈이는 불에 타기 전에 미로를 탈출해야 한다.
매 분마다 .으로 되어 있는 곳으로만 이동할 수 있다.

1. 큐를 두 개 사용하여, 시작시간을 1로 지정
   queue_fire: 불의 이동(F->1), queue_hoon: 지훈의 이동(J->1)
2. while queue_fire:을 끝낸 후, while queue_hoon:에서 아래 조건에 따라 이동 가능!

• 범위 안에 있음
  • 벽이 아니고, 방문하지 않았으면
    - 불이 붙지 않았거나, 불이 붙기 전이면
• 범위 밖이면 탈출, 현재 값 리턴

3. 만약 while queue_hoon: 가 끝까지 실행되면 탈출 불가

정답

from collections import deque
import sys
input = sys.stdin.readline

def BFS():
    while queue_fire: # fire
        x, y = queue_fire.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                if arr[nx][ny]!='#' and fire[nx][ny]==0:
                    queue_fire.append((nx, ny))
                    fire[nx][ny] = fire[x][y]+1

    while queue_hoon: # jihoon
        x, y = queue_hoon.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < R and 0 <= ny < C: 
                if arr[nx][ny]!='#' and hoon[nx][ny]==0:
                    if fire[nx][ny]==0 or hoon[x][y]+1<fire[nx][ny]:
                        queue_hoon.append((nx, ny))
                        hoon[nx][ny] = hoon[x][y]+1
            else: # escape
                return hoon[x][y]

    return 'IMPOSSIBLE'

R, C = map(int, input().split())
arr = [ list(input().strip()) for _ in range(R)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
fire = [[0] * C for _ in range(R)]
hoon = [[0] * C for _ in range(R)]
queue_fire, queue_hoon = deque(), deque()

for i in range(R):
    for j in range(C):
        if arr[i][j]=='F':
            queue_fire.append((i,j))
            fire[i][j]=1
        if arr[i][j]=='J':
            queue_hoon.append((i,j))
            hoon[i][j]=1

print(BFS())

제출