백준 13549번: 숨바꼭질 3

✔ 풀이를 위한 아이디어

0-1 너비 우선 탐색 (BFS + 다익스트라)

✔ 오답 코드 [틀렸습니다]

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())

visited = [0]*100001
heap = [(0, N)]
visited[N] = 1

while heap:
    cur_time, cur_pos = heapq.heappop(heap)
    if cur_pos == K:
        print(cur_time)
        break
    if cur_pos > 0 and not visited[cur_pos-1]:
        heapq.heappush(heap, (cur_time+1, cur_pos-1))
        visited[cur_pos-1] = 1
    if cur_pos < 100000 and not visited[cur_pos+1]:
        heapq.heappush(heap, (cur_time+1, cur_pos+1))
        visited[cur_pos+1] = 1
    if cur_pos*2 <= 100000 and not visited[cur_pos*2]:
        heapq.heappush(heap, (cur_time, 2*cur_pos))
        visited[cur_pos*2] = 1

접근 방식

• 0-1 너비 우선 탐색 이라는 알고리즘이 따로 존재하는 줄 알고 구현에 앞서 알고리즘을 공부하려 했으나, BFS와 다익스트라 알고리즘을 합쳐놓은 것이라는 것을 깨닫고 스스로 구현해보았다.
• 가중치가 0 또는 1이기 때문에, 이전에 풀었던 가중치가 1로 일정한 숨바꼭질 문제와는 풀이 방식이 조금 달라야 했다. ( https://velog.io/@dlehdtjq00/백준-1697번-숨바꼭질 )
• 시간을 0초만 쓰면서 목적지에 도달하는 경우를 우선적으로 처리해야 하므로, 인접한 지점부터 탐색해나가는 BFS만으로는 부족하다.
• 따라서 다익스트라 알고리즘에서 했듯이 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 반환하는 과정이 필요하며, 이에 따라 최소 힙 (Heap) 을 사용하였다.
• 최소 시간 테이블을 따로 사용하는 대신, 최소 힙에 현재까지의 시간을 같이 넘겨주는 방식을 택하였다. 이는 다익스트라와 다르게 먼저 방문한 지점이 최소 시간을 갖기 때문에 가능하다.

한계점

• 다만, 해당 코드는 계속해서 '틀렸습니다'를 받게 되었다. 해당 코드가 틀린 반례를 찾지 못해 헤매던 중, N=1, K=16 일때 제대로된 답을 도출하지 못한다는 것을 알아냈다.
• 원래라면 1->2->4->8->16 으로 0초만에 도달해야 하는데, 나의 코드는 1초라는 오답을 도출하였고, 원인을 파악하기 위해 매 while문마다 heap에 들어 있는 내용물을 출력하도록 해보았더니 아래 사진의 왼쪽과 같은 결과가 나왔다.
  
• 위 사진의 오른쪽과 같은 결과가 나오지 않은 이유는 2번째 줄만 봐도 알 수 있다. (0, 2) 라는 요소가 들어오지 않고 (1, 2) 라는 요소가 들어왔기 때문이다. 내가 짠 코드를 잘 뜯어보면, 한번의 while문 안에서 위치를 [+ 1] 하는 경우가 [X 2] 하는 경우보다 먼저 체크되는 것을 알 수 있다.
• 이에 따라 첫 번째 if문에서 위치를 [+ 1] 하는 경우를 체크하며 힙에 (1, 2)를 넣어주고, visited[2]를 1로 바꿔준다. 이후, visited[2]가 1이기 때문에 위치를 [X 2] 하는 경우인 세 번째 if문에 들어갈 수 없게 되고, 따라서 (0, 2)가 들어가지 못하는 결과로 이어지게 된다.
• 처음에는 범위 값을 100,000 까지가 아닌 200,000까지로 잡아야 하는지도 고민했으나, 100,000을 초과했다가 [- 1] 를 반복해 돌아오는 것보다 [- 1]을 먼저 하고 100,000에 가까운 값까지
  [X 2]하여서 가는 것이 더 효율적이기 때문에 그럴 필요는 없었다.

✔ 정답 코드

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())

visited = [0]*100001
heap = [(0, N)]
visited[N] = 1

while heap:
    cur_time, cur_pos = heapq.heappop(heap)
    if cur_pos == K:
        print(cur_time)
        break
    ############# 이 부분만 앞쪽으로 빼주면 된다 #############
    if cur_pos*2 <= 100000 and not visited[cur_pos*2]:
        heapq.heappush(heap, (cur_time, 2*cur_pos))
        visited[cur_pos*2] = 1        
    ######################################################    
    if cur_pos > 0 and not visited[cur_pos-1]:
        heapq.heappush(heap, (cur_time+1, cur_pos-1))
        visited[cur_pos-1] = 1
    if cur_pos < 100000 and not visited[cur_pos+1]:
        heapq.heappush(heap, (cur_time+1, cur_pos+1))
        visited[cur_pos+1] = 1

• 해결 방법은 단순하다. (1, 2) 라는 요소 대신에 (0, 2) 라는 요소를 넣어야 했듯이, 같은 지점을 방문할 때는 [X 2] 하는 경우를 우선적으로 처리해주면 되는 것이다. 따라서 세 번째 if문을 맨 앞으로 빼주면 된다.
• 가중치가 1로 일정한 백준 1697번: 숨바꼭질 문제에서 처럼 덱 (Deque)를 활용해서도 풀 수 있다. 해당 방식의 풀이는 아래와 같다.

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
MAX = 10 **5
visited = [-1] * (MAX+1)  # 일반적인 visited 배열의 역할 + 최소시간 테이블의 역할

queue = deque([N])
visited[N] = 0 

while queue:
    cur_pos = queue.popleft()
    if cur_pos == K:
        print(visited[cur_pos])
        break
    for x_pos in (2*cur_pos, cur_pos-1, cur_pos+1):
        if 0 <= x_pos <= MAX and visited[x_pos] == -1:
            if x_pos == 2*cur_pos:  # 이 경우에도 [X 2]의 경우를 먼저 처리해주자.
                visited[x_pos] = visited[cur_pos]
                queue.appendleft(x_pos)  # deque 모듈의 appendleft를 활용해 최소 힙을 대신 (어짜피 0이랑 1만 가지고 비교하므로)
            else:
                visited[x_pos] = visited[cur_pos] + 1
                queue.append(x_pos)

• '출력 초과' 는 실수로 디버깅 용으로 추가한 코드를 함께 제출해서 받은 것이다.
• '틀렸습니다' 와 '맞았습니다' 를 반복하며 알아낸 것들은 모두 위에서 서술하였다. 생각보다 쉬우면서도 골치아팠던 문제인 것 같다.

✔ 추가로 공부해볼 것들

• 좀 더 일반적인 경우의 0-1 BFS (꼬리물기 문제도 생각해보기, 이 블로그의 다른 글도 공부하기) : https://m.blog.naver.com/chogahui05/221517208122
• 0-1 BFS의 시간복잡도 (알고리즘 수강 이후에 다시 보기) : https://justicehui.github.io/medium-algorithm/2018/08/30/01BFS/
• 피보나치 힙과 휴리스틱에 대한 탐구