13549. [Python]숨바꼭질 3

1. 문제

 

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

 

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 512MB
• 다익스트라

 

3. 파이썬 코드

 

import heapq
# 다익스트라
def dijkstra(start):
    queue = []
    # 우선순위 큐
    heapq.heappush(queue, (0,start))
    while queue:
        # 시간, 위치
        time, now = heapq.heappop(queue)
        # +1 한 값, -1 한 값, *2 한 값
        next_add = now+1
        next_min = now-1
        next_multi = now*2
        # +1 한 값이 100000 이하일 경우
        if next_add <= 100000:
            # 거리값 비교하여 시간이 작은 경우 갱신 후 리스트 추가
            if distance[next_add] > time + 1:
                distance[next_add] = time + 1
                heapq.heappush(queue, (time+1, next_add))
        # -1 한 값이 0 이상일 경우
        if next_min >= 0:
            # 거리값 비교하여 시간이 작은 경우 갱신 후 리스트 추가
            if distance[next_min] > time + 1:
                distance[next_min] = time + 1
                heapq.heappush(queue, (time+1, next_min))
        # *2힌 값이 100000 이하인 경우
        if next_multi <= 100000:
            # 거리값 비교하여 시간이 작은 경우 갱신 후 리스트 추가
            if distance[next_multi] > time:
                distance[next_multi] = time
                heapq.heappush(queue, (time, next_multi))

start, target = map(int,input().split())

if start == target:
    print(0)
else:
    distance = [10**9] * 100001

    dijkstra(start)

    print(distance[target])

 

4. 문제를 풀고난 후 생각

 

• 앞선 숨바꼭질 문제들과 비슷하지만 *2를 진행했을 때는 시간초가 늘어나지 않는 점을 이용하여 시간 값을 갱신한다는 점이 다르다.
• 다익스트라 알고리즘 특성상 최적의 경로를 찾기 떄문에 time 값이 제일 작은 것을 우선으로 탐색을 진행시킨다.
• 다익스트라 알고리즘을 완전히 돌았을 경우 최적의 시간이 갱신돼있기 때문에 문제를 쉽게 해결할 수 있다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 다익스트라 알고리즘