16953. A->B

Problem

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

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

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

Input

첫째 줄에 A,B(1<=A<B<=10^9)가 주어진다.

Output

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

풀이

너비 우선 탐색(bfs)를 사용하여 풀 수 있다.

A에서부터 시작해서 2를 곱한 노드와 1을 수의 오른쪽에 추가한 경우로 경로를 탐색해 나가면 된다.

[종료 조건]

• 연산의 결과가 B와 같다.
• 연산의 결과가 B보다 크다.

코드

a, b = map(int, input().split())

def bfs () :
  q = list()
  q.append((0,a)) # 연산의 개수, 현재 수
  
  while q :
    count, num = q.pop(-1)
    
    if num == b :
      return count + 1
    elif num > b :
      continue

    # 1. 2곱하기
    q.append((count+1, num*2))
    # 2. 1을 수의 가장 오른쪽에 추가한다.
    q.append((count+1, num*10 + 1))

  return -1

print(bfs())