[python] 백준 16953 A->B

https://www.acmicpc.net/problem/16953

16953번: A → B

 

문제 해결

• 전형적인 가장 쉬운 완전탐색 문제라 생각했다.
• bfs가 dfs보다 편할 것이라 생각했다.
• heapq, deque 어떤 것을 써도 상관 없다.(근데 deque가 속도가 더 빨랐다.)

CODE

from collections import deque
import sys
INF = sys.maxsize
a, b = map(int, input().split())
ans = INF
def bfs():
    global ans
    que = deque()
    que.append((a,0))

    while que:
        x, cnt = que.popleft()
        if x == b:
            ans = min(ans,cnt)
        elif x < b:
            que.append((10*x+1, cnt+1))
            que.append((2*x,cnt+1))
bfs()
if ans == INF:
    print(-1)
else:
    print(ans+1)