[백준] 16953: A→B python 구현 / Greedy, BFS

문제

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

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

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

 

풀이

숨바꼭질 문제들( 숨바꼭질, 숨바꼭질3 )과 매우 유사함 !

BFS로 풀면 된다.

주의 ! A, B (1 ≤ A < B ≤ 109) 를 잘 지키자.

 

CODE

from collections import deque

A, B = map(int, input().split())

def bfs(n):
    queue = deque()
    queue.append((n, 0))

    while queue:
        n, time = queue.popleft()
        ntime = time + 1

        for i in range(2):
            if not i:
                num = n * 2
            elif i:
                num = int(str(n) +'1')
            
            if num < 1 or num > 10**9: continue
            if num == B:
                return ntime + 1
            
            queue.append((num, ntime))

    return -1

print(bfs(A))