13549-백준-숨박꼭질3

1. 문제 출처

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

13549번: 숨바꼭질 3

2. 풀이

데이크스트라 알고리즘을 이용한 문제이다...

여기서 주의 할점은 그래프 배열의 사이즈를 max(n,k)로 하는 것이아니라 100000로 해야한다. 

왜냐하면 max 를 사용해서 지정 할경우 해당 범위를 지나서 도착하는 것이 더빠를 수 있는데 그것을 계산하지 못하기 때문이다. 

import heapq
#입력
n,k = map(int, input().split())
# 사이즈는 n,k의 최대값
size = 100000
graph = [[] for _ in range(size+1)]
distance = [float('inf')] * (size+1)

# 그래프 초기화
for idx in range(size+1): 
    if (idx * 2) <= size and idx !=0:
        graph[idx].append([0,2*idx])
        
    if idx !=size:
        graph[idx].append([1,idx+1])
        
    if idx != 0 :
        graph[idx].append([1,idx-1])
        
#데이크스트라 알고리즘
def di(start):
    #우선순위 큐
    q = []
    # 큐에 값 넣기
    heapq.heappush(q,[0,start])
    distance[start] = 0
    # 큐가 비을 때 까지
    while q:
        dist , node = heapq.heappop(q)
        
        if distance[node] < dist:
            continue
        
        for w,ln in graph[node]:
            cost = w + dist
            if distance[ln] > cost:
                distance[ln] = cost
                heapq.heappush(q,[cost , ln])
di(n)
print(distance[k])