B)1697

숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

사실, 이것보다 상위 문제인 숨바꼭질 문제를 이미 푼 상황이라서, 그 문제를 약간 수정해서 쉽게 푼 문제였다.
이 문제 또한 다익스트라를 사용하면 풀 수 있는 문제이다. 노드간의 거리는 모두 같지만, 순간이동을 할 경우, 2배의 칸을 단 1초만에 움직일 수 있기 때문에, 다익스트라를 적절히 활용하면 풀 수 있을 것 이라고 생각했다.

구현(Dijkstra)
1.현재 수빈이의 위치를 2배로 적용한다.
2.만약, 2배한 위치가 적절한 범위 내라면, 큐에 삽입
3.2배한 위치가 적절하지 않다면, +1,-1 연산 수행
4.동생의 위치에 도달할 때 까지 반복

코드를 살펴보자

import sys
import heapq

input = sys.stdin.readline

n, k = map(int, input().split())
visited = [False] * 100001 #최대 좌표
visited[n] = True
queue = []
heapq.heappush(queue,(0,n)) #현재 수빈이 위치

while queue:
    dist, node = heapq.heappop(queue)
    if node == k: #동생의 위치라면,
        print(dist)
        break
    next = node * 2
    if next < len(visited) and not visited[next]:
        visited[next] = True
        heapq.heappush(queue, (dist + 1, next))

    for i in (node + 1, node - 1):
        if i >= 0 and i < len(visited) and not visited[i]:
            visited[i] = True
            heapq.heappush(queue, (dist + 1, i))

여기서 2배 연산을 먼저 해주는 이유는, 5 -> 10으로 가는 경우, +1이나 -1 연산을 먼저 하게 된다면, 2배를 하면 바로 도달할 수 있는데도 불구하고, 불필요한 연산을 반복하게 되기 때문에, 당장에 가장 많이 움직일 수 있는 경우를 먼저 따져주는 것이다.
(여기서 한 부분만 바꾸면 골드 숨바꼭질 문제를 풀 수있다.)