[Problem Solving] 백준 4179 불!

백준 4179 불! 문제에 대한 자세한 설명은 다음의 링크를 참고해주시기 바랍니다. 문제 설명

4179번: 불!

미로 안에 지훈이와 불이 붙은 위치가 주어졌을 때 지훈이가 탈출 여부를 확인하고, 탈출할 수 있다면 최단 시간을 출력하는 문제입니다. 그래프 탐색 문제로 대부분의 문제들은 dfs, bfs를 하나의 대상에게 적용시켰지만 불! 문제는 불과 지훈이를 대상으로 그래프 탐색을 진행한다는 점에서 차이가 있었습니다.

 

다음은 문제 해결 순서입니다.

1. maps를 순환하며 지훈이의 위치와 불의 위치를 deque()에 넣어주고, visited의 값을 1로 초기화해준다. (visited[x][y] = 0은 아직 방문하지 않은 노드라는 뜻이다)
2. 지훈이의 deque와 visited를 사용하여 지훈이의 이동 경로와 시간을 jihon_visited에 저장한다.
3. 불의 deque와 visited를 사용하여 불의 이동 경로와 시간을 fire_visited에 저장한다.
4. 지훈이와 불의 visited를 순환하며 지훈이의 최단 시간하여 결과로 반환한다.

visited의 값을 True, False를 사용하지 않고, 0을 사용한 이유는 bfs 알고리즘을 사용하였을 경우 거리에 비례해서 visited의 값을 초기할 수 있기 때문입니다. 문제에서 최단 시간은 곧 거리와 같은 의미이므로 0과 정수로 visited를 초기화한다면 visited를 순환하며 비교하는 것만으로도 최단 시간을 계산할 수 있습니다.

 

다음은 이해를 도와줄 예시입니다.

 

maps = [
  ['#', '#', '#', '#', '#'],
  ['#', '.', '.', '.', '#'], 
  ['F', '.', 'J', '.', '#'], 
  ['#', 'F', '#', '.', '.'],
  ['#', '#', '#', '#', '.']]
  
[[0, 0, 0, 0, 0], # jihon_visited
 [0, 3, 2, 3, 0],
 [3, 2, 1, 2, 0], 
 [0, 3, 0, 3, 4], 
 [0, 0, 0, 0, 5]]
[[0, 0, 0, 0, 0], # fire_visited
 [0, 3, 4, 5, 0],
 [1, 2, 3, 4, 0], 
 [0, 1, 0, 5, 6], 
 [0, 0, 0, 0, 7]]

 

maps를 참고하며 jihon_visited, fire_visited를 살펴보면 둘을 비교하는 것만으로도 지훈이가 4분에 탈출할 수 있다는 것을 확인할 수 있습니다.

 

위의 예시를 통해 다음의 조건을 확인할 수 있습니다. 

1. jihon_visited[x][y] < fire_visited[x][y]일 경우 불의 도착이 더 늦기 때문에 지훈이는 해당 위치에서 안전한다.
2. x == 0 or y == 0 or x == (r-1) or y == (c-1)일 경우에 지훈이의 도착 시간을 계산한다. 이때, answer에는 도착시간이 짧은 시간을 초기화해줘야 한다.

위의 조건에서 2번의 경우는 가장자리에 지훈이가 안전하게 도착할 경우 위의 예시에서는 (4, 5)가 결괏값으로 나올 수 있는데 이때의 최단 시간을 answer에 저장해야 한다는 조건입니다.

 

이렇게 조건을 만들어서 정답을 맞힐 수 있다면 이상적이었겠지만 위 두 조건만을 만족했을 경우 책점 중 (71%)에서 "틀렸습니다"라는 결과를 가지게 됩니다. 

 

다음의 예시를 통해서 빠진 조건을 확인할 수 있습니다.

 

maps = [
  ['#', '#', '#', 'F', '#'],
  ['#', 'J', '#', '.', '#'], 
  ['.', '.', '#', '.', '#'], 
  ['#', '.', '#', '.', '.'],
  ['#', '#', '#', '#', '#']]
 
[[0, 0, 0, 0, 0], # jihon_visited
 [0, 1, 0, 0, 0],
 [3, 2, 0, 0, 0],
 [0, 3, 0, 0, 0],
 [0, 0, 0, 0, 0]]
[[0, 0, 0, 1, 0], # fire_visited
 [0, 0, 0, 2, 0],
 [0, 0, 0, 3, 0],
 [0, 0, 0, 4, 5],
 [0, 0, 0, 0, 0]]

 

maps를 확인해보면 애초에 지훈이와 불이 만날 수 없는 경우의 조건을 처리해주지 않았기 때문에 위의 예시의 결괏값은 "IMPOSSIBLE"이 나오게 됩니다. 따라서 불이 지나갈 수 없는 곳에서도 answer의 값을 계산해줘야 하기 때문에 위의 조건에서 1번을 다음과 같이 수정합니다.

• jihon_visited[x][y] < fire_visited[x][y] or fire_visited[x][y] == 0

다음은 위의 조건들을 고려하여 작성한 코드입니다.

 

# 백준 No.4179 불!
import sys
from collections import deque

input = sys.stdin.readline

def bfs(queue, visited):

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

  while queue:
    x, y = queue.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < r and 0 <= ny < c:
        if visited[nx][ny] == 0 and maps[nx][ny] != '#':
          visited[nx][ny] = visited[x][y] + 1
          queue.append((nx, ny))
  return visited

r, c = map(int, input().split())
maps = []

for _ in range(r):
  maps.append(list(input().strip()))

answer = 2001
fire_q, jihon_q = deque(), deque()
fire_visited, jihon_visited = [[0] * c for _ in range(r)], [[0] * c for _ in range(r)]

for x in range(r):
  for y in range(c):
    if maps[x][y] == 'J':
      jihon_q.append((x,y))
      jihon_visited[x][y] = 1
    elif maps[x][y] == 'F':
      fire_q.append((x,y))
      fire_visited[x][y] = 1

jihon_visited = bfs(jihon_q, jihon_visited)
fire_visited = bfs(fire_q, fire_visited)

for x in range(r):
  for y in range(c):
    if jihon_visited[x][y] > 0:
      if jihon_visited[x][y] < fire_visited[x][y] or fire_visited[x][y] == 0:
        # jihon is safe
        if x == 0 or y == 0 or x == (r-1) or y == (c-1):
          answer = min(answer, jihon_visited[x][y])

print(answer if answer != 2001 else "IMPOSSIBLE")

 

그래프 탐색은 어느 정도 자신감이 있어서 빠르게 해결할 수 있다고 생각했지만 난이도가 있어서 해결하는데 애를 먹었습니다. 하지만 삽질을 하는 과정에서 bfs에 대한 이해가 조금 더 늘었고, 그래프 탐색 유형의 문제가 무조건 알고리즘을 진행하면서 문제를 해결하는 게 아니라 결과들을 유연하게 활용하여 해결할 수 있다는 것을 다시 한번 느꼈습니다.