[백준 / Python] 16953번 A → B

백준 16953 [ A → B ] 문제 python 풀이

---

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

 

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

 

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

예제

입력	출력
2 162	5
4 42	-1
1000 40021	5

---

from collections import deque
A, B = map(int, input().split())

# A를 B로만들기 
# 1. 2를곱하거나 
# 2. 숫자 뒷 자리에 1을 추가 (숫자 * 10 + 1)

queue = deque()


queue.append((A, 1))

while True:
    if len(queue) == 0:
        print(-1)
        break
    tempA, tempCnt = queue.popleft()
    if tempA > B:
        continue
    if tempA == B:
        print(tempCnt)
        break
    queue.append((tempA*2, tempCnt + 1))
    queue.append((tempA*10 + 1, tempCnt + 1))

bfs풀이입니다.