[boj 13549] [Python] 숨바꼭질 3

문제 링크

우선 나는 이 알고리즘의 분류를 알고 접근했다. 모르고 접근했으면 더 해맸을 텐데, 이번주에 대회도 있고 해서 유형 하나라도 더 확실하게 알아가려고 알고 풀었다.

다익스트라 알고리즘 이용.

다익스트라 알고리즘은 현재 노드에서 가능한 노드들에 대해 반복 돌리면서 최솟값 경로 체크하는 부분이 있다.

그것을 이 문제에서는 현재노드-1 노드, 현재노드+1 노드, 현재노드*2 노드 3가지만 탐색하면 된다.

적절한 종료조건을 설정하지 않으면 엄청나게 (10만까지) 뻗어 나가는 걸 볼 수 있으므로 종료조건에 유의한다.

이번 문제는 그래프가 오히려 간소화된 것이라고 볼 수 있다.

코드는 아래와 같다.

# 13549 숨바꼭질 3

# 걷기 x -> x-1 or x+1 (1초 소요)
# 순간이동 x -> 2*x (0초 소요)

import sys
import heapq

INF = sys.maxsize

n, k = map(int, input().split())

# 흠.. distance 초기화를 어케하나
# 최대 노드개수로 초기화 
d = [INF] * 100001
queue = []

def dijkstra(n, k):
    d[n] = 0    # 시작 값을 0으로 초기화
    heapq.heappush(queue, [d[n], n])

    while queue:
        cur_d, cur_dest = heapq.heappop(queue)
        
        if d[cur_dest] < cur_d:
            continue
        if cur_dest == k:
            return
        
        for i in range(3):
            if i == 0:
                next_dest = int(cur_dest)-1
                next_d = 1
            elif i == 1:
                next_dest = int(cur_dest)+1
                next_d = 1
            else:
                next_dest = int(cur_dest) * 2
                next_d = 0
            
            if next_dest < 0 or next_dest > 100000:
                continue

            # 3개에 대해 탐색
            tmp_d = next_d + cur_d

            if d[next_dest] > tmp_d:
                d[next_dest] = tmp_d
                heapq.heappush(queue, [tmp_d, next_dest])

dijkstra(n, k)
print(d[k])