🔥

문제

윌리는 좌표 X에서 좌표 Y까지 포탈을 이용하여 이동하려고 한다. 포탈을 이용하면 좌표 A에서 좌표 A+1, A-1, 2*A 중 한 좌표로 이동할 수 있다. X와 Y를 입력받아 좌표 X에서 좌표 Y까지 이동하기위한 포탈의 최소 사용 횟수를 구해보자

입력

첫 줄에 X,Y가 공백을 사이에 두고 주어진다. 두 값 모두 0 이상 10만 이하이다.

출력

좌표 X에서 좌표 Y까지 이동하기위한 포탈의 최소 사용 횟수를 출력한다.

예제 1 입력

5 17

예제 1 출력

4

예제 2 입력

3 100

예제 2 출력

6

Source

from collections import deque

x, y = map(int, input().split())
q = deque()
depth = [0 for _ in range(200001)]

depth[x] = 1
q.append(x)

while(True):
	if(len(q) == 0):
		break
	x = q.popleft()
	if(x + 1 <= 200000 and depth[x + 1] == 0):
		depth[x + 1] = depth[x] + 1
		q.append(x + 1)
	if(x - 1 >= 0 and depth[x - 1] == 0):
		depth[x - 1] = depth[x] + 1
		q.append(x - 1)
	if(x * 2 <= 200000 and depth[x * 2] == 0):
		depth[x * 2] = depth[x] + 1
		q.append(x * 2)
print(depth[y] - 1)

참고