난이도

Gold 5

문제

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

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

입력

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

출력

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

예제 입력

5 17

예제 출력

2

해설 및 후기

우선 예제는 수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

BFS로 풀이했다. 데이크스트라로 풀이하는 것이 정석인 것 같지만, 우선 생각나는대로 BFS를 이용해 풀이했더니 그냥 맞았다.

일단은 이동하는데에 우선 순위가 있다. 순간 이동은 시간을 소모하지 않으므로, 우선순위가 제일 높아야 한다. 따라서 순간이동 하는 경우를 appendleft하여 같은 depth 내에서 무조건 걷는 것보다 빠르게 사용하도록 했다. 우선순위 큐를 사용하면 더 효율적으로 이를 관리할 수 있을 것 같다.

제출 코드

import collections

n, k = map(int, input().split())
queue = collections.deque()

isVis = [False for _ in range(100001)]
isVis[n] = True
queue.append([n,0])

while(queue):
    x, depth = queue.popleft()
    #print(x,depth)
    if(x == k):
        print(depth)
        exit()
    else:
        if(x*2 >= 0 and x*2 <= 100000):
            if(not isVis[x*2]):
                isVis[x*2] = True
                queue.appendleft([x*2, depth])
        for y,d in [[x-1,depth+1],[x+1,depth+1]]:
            if(y>=0 and y<=100000):
                if(not isVis[y]):
                    isVis[y] = True
                    queue.append([y,d])