[Gold IV] 불! - 4179 (BFS)

[Gold IV] 불! - 4179

문제 링크

성능 요약

메모리: 70840 KB, 시간: 2332 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

#.지나갈 수 있는 공간
#J지훈이 위치
#F불 위치
from collections import deque
r, c = map(int,input().split())
graph = []
for i in range(r):
  graph.append(list(input()))

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

minsu_visited = [[0] * c for i in range(r)] #방문한 시간
fire_visited = [[0] * c for i in range(r)] #방문한 시간

minsu = deque() #민수 좌표
fire = deque() #불 좌표

for i in range(r):
  for j in range(c):
    if graph[i][j] == "J":
      minsu.append((i,j))
      minsu_visited[i][j] = 1 #0분부터 시작인데 결국 탈출할 시 1분을 더해줘야 하기 때문.
    elif graph[i][j] == "F":
      fire.append((i,j))
      fire_visited[i][j] = 1

def bfs():
  while fire:
    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 not fire_visited[nx][ny] and graph[nx][ny] != "#":
          fire_visited[nx][ny] = fire_visited[x][y] + 1
          fire.append((nx,ny))
  while minsu:
    x, y = minsu.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < r and 0 <= ny < c:
        if not minsu_visited[nx][ny] and graph[nx][ny] != "#":
          if not fire_visited[nx][ny] or fire_visited[nx][ny] > minsu_visited[x][y] + 1:
            minsu_visited[nx][ny] = minsu_visited[x][y] + 1
            minsu.append((nx, ny))
      else: #탈출 시
        return minsu_visited[x][y]
  return "IMPOSSIBLE" #미탈출
print(bfs())

민수(지훈)가 불에 닿지 않는 것을 체크하려면, 민수 한 번 이동 후, 불도 한 번 이동하는 식으로 동시에 bfs를 사용해야 하나 싶었는데, 구글링을 통해 알아낸 결과, 각자 fire_visited, minsu_visited에 몇 분에 해당 위치로 갔는지를 저장하여 체크를 해주는 방식으로 해결이 가능했다.

1. 민수의 좌표를 구한 후 minsu_visited 해당 좌표에 1분을 더해준다. (원래는 해당 좌표부터는 0분이고, 가장자리에서 탈출할 당시에 1분이 더해지는 것 같은데 미리 넣어주는 것이 방문체크도 할 수 있어 비교하기가 편하다.(시작부터 1분 일수도?..))

2. 불의 좌표를 구한 후 fire_visited 해당 좌표에 1분을 더해준다.

3.bfs 실행

4.fire 부터 먼저 큐를 돌며 좌표마다 몇 분에 불이 번지는지 모두 체크한다.

5.minsu가 큐를 돌며 다음으로 갈 수 있는 장소가 불이 번진 시간보다 작으면 이동을 해주어 minsu_visited에 1분을 추가한다.

6.결국 가장자리에 도착하면 그다음 nx, ny좌표는 (0~r-1),(0~c-1)좌표에서 탈출되기 때문에 else문으로 minsu_visited에서 현재 민수 좌표를 리턴해주면 된다.

7.만약에 좌표에서 탈출하지 못하고 while문을 모두 돌게 되면, 탈출하지 못한 것이므로 IMPOSSIBLE 출력