BOJ 16953. A->B(python)

BOJ 문제 16953. A->B

문제링크

문제설명

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

2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입출력 예

솔루션

1. bfs를 이용한 완전탐색으로 구현

2. 연산 중 B를 넘어가면 무시

3. B를 찾거나 Queue가 빌 때까지 연산을 수행한다.
   
   

코드

from collections import deque

a, b = map(int, input().split())
q = deque()
q.append((a, 1))
result = -1
while q:
    x, count = q.popleft()
    # 연산으로 b를 만들면 연산 중지
    if x == b:
        result = count
        break
    # b보다 커지면 연산하지 않는다.
    if x > b:
        continue
    # 2를 곱하는 경우
    q.append((x*2, count+1))
    # 숫자 오른쪽에 1을 더하는 경우
    q.append((x*10+1, count+1))

print(result)