[백준] 4179. 불!

불불불~~~!

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

제출 코드

• 7% 틀렸습니다: 지훈이 방문체크를 하였나?
• 21% 틀렸습니다: 구현 상 문제가 있다.

지훈이와 불은 매 분마다 한 칸씩 수평 또는 수직으로 이동한다.

위의 조건을 만족하면 21% 틀렸습니다에서 빠져나올 수 있다.

• 불이 지훈이보다 먼저 이동하도록 한다. (불의 이동이 먼저냐 지훈이의 이동이 먼저냐..)

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

r, c = map(int, input().split())
table = [list(input().rstrip()) for _ in range(r)]
visited = [[False] * c for _ in range(r)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
jx, jy= 0, 0 # J는 입력에서 하나만 주어진다.
fire = [] # 

def bfs():
  
    qq = deque()
    # movements, x, y
    qq.append([0, jx, jy])
    visited[jx][jy] = True

    ffq = deque()
    for fx, fy in fire:
        # x, y
        ffq.append([fx, fy]) 
  
    while qq:
        fq = ffq
        q = qq
        ffq = deque()
        qq = deque()

	# 불 먼저 이동 (불의 위치를 넣어놓은 fq queue)
        while fq:
            _fx, _fy = fq.popleft()
           
            for i in range(4):
                ffx = _fx + dx[i]
                ffy = _fy + dy[i]

                if ffx < 0 or ffy < 0 or ffx >= r or ffy >= c: continue
                # 불은 벽을 지나갈 수 없고, 이미 불이 난 곳을 또 지나갈 필요가 없다.
                if table[ffx][ffy] == '#' or table[ffx][ffy] == 'F': continue
                table[ffx][ffy] = 'F' # 불은 이동하면 배열에 표시한다.
                ffq.append([ffx, ffy]) # 다른 queue에 이동한 불의 위치를 저장한다.
        # 지훈이 이동
        while q:
            movements, _x, _y = q.popleft()

	    # 지훈이가 가장자리에 도착했으므로 탈출 성공 (아예 가장자리 밖으로 나가야 탈출이기 때문에 이동횟수 + 1 을 해준다.
            if _x == 0 or _y == 0 or _x == r - 1 or _y == c - 1:   >   
                return movements + 1
              
            for i in range(4):
                x = _x + dx[i]
                y = _y + dy[i]

                if x < 0 or y < 0 or x >= r or y >= c: continue
                # 벽인 곳도 가장자리인 곳으로도 이동할 수 없다.
                if table[x][y] == '#' or table[x][y] == 'F': continue
                if visited[x][y]: continue
                visited[x][y] = True # '7% 틀렸습니다' 원인, 지훈이 방문체크 안하면 7%
                qq.append([movements + 1, x, y])

    return "IMPOSSIBLE"

for i in range(r):
    for j in range(c):
        if table[i][j] == 'J':
            jx, jy = i, j
            table[i][j] = '.'
        if table[i][j] == 'F':
            fire.append([i, j])

print(bfs())