[BaekJoon] 백준 16953번 : A to B

16953번 : A → B

어떤 작업을 해 나가면서 그 작업 횟수의 최소를 물어본다면..

그래프를 그려 탐색하면 된다..

최대 10⁹ 까지 가능하기 때문에 미리 그래프를 그려두고 탐색하기 보다 만들어 가면서 탐색을 하면 된다.

큐에 저장할 때 연산 횟수도 함께 저장을 해주면 된다.

연산의 특성 상 트리가 생성 되기 때문에 방문 노드를 따로 관리 할 필요는 없다.

---

from collections import deque


def solution(start, goal):
	cnt = 1
	queue = deque([[start, cnt]])

	while queue:
		curNode, curCnt = queue.popleft()

		if curNode == goal:
			print(curCnt)
			return

		leftChild = curNode * 2
		rightChild = curNode * 10 + 1

		if leftChild <= 10**9:
			queue.append([leftChild, curCnt + 1])

		if rightChild <= 10**9:
			queue.append([rightChild, curCnt + 1])

	else:
		print(-1)
		return


n, m = map(int, input().split())
solution(n, m)