[백준/4179/5427] 불! (Python)

Problem : https://www.acmicpc.net/problem/4179

4179번: 불!

 

https://www.acmicpc.net/problem/5427

5427번: 불

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00 : 13 : 27

 

---

 

문제 설명

 

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

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

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

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

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

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

 

입력 및 출력

 

입력

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

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

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

#: 벽
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간
J는 입력에서 하나만 주어진다.

 

출력

 

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

 

입력 예시

 

4 4
####
#JF#
#..#
#..#

 

출력 예시

 

3

 

 

---

 

풀이

 

복습 겸(?) 풀어본 문제. 분명히 예전에 풀었던 기억이 났고... 실제로도 그랬다. 골때리는 점은, 이게 블로그에 포스팅이 안 되 있었다. 실환가?

 

핵심은 BFS를 돌리되, 불을 먼저 돌려 불의 진행 시점을 먼저 알고 있어야 한다는 점이다. 지훈이가 경로 탐색을 진행할 때, 자신의 시점보다 더 일찍 불이 방문했다면, 혹은 동시에 방문한다면 그 지점은 방문할 수 없다. 따라거 불 -> 지훈이 순으로 경로 탐색을 진행하고, 만일 지훈이의 경우 지도 밖으로 나갈 수 있다면 그 해답을 출력하면 된다.

 

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline
dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]
MAX = float('inf')
R, C = map(int, input().split())
map_list = [input().strip() for _ in range(R)]
visited = [[MAX]*C for _ in range(R)]
fq = deque()
jq = deque()

def init() :
  for r in range(R) :
    for c in range(C) :
      if map_list[r][c] == 'F' :
        fq.append((r, c, 0))
        visited[r][c] = 0
      elif map_list[r][c] == 'J' :
        jq.append((r, c, 0))

def bfs(q, mode = False) :    
  while q :
    r, c, d = q.popleft()
    for k in range(4) :
      ar, ac = r + dr[k], c + dc[k]
      if -1 < ar < R and -1 < ac < C :
        if map_list[ar][ac] != '#' and visited[ar][ac] > d + 1 :
          visited[ar][ac] = d + 1
          q.append((ar, ac, d+1))
      elif mode :
        return d + 1
  return MAX

init()
_ = bfs(fq)
result = bfs(jq, mode = True)

print(result if result < MAX else 'IMPOSSIBLE')