[BOJ][python] 16953. A → B

 

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

16953번: A → B

---

💡IDEA

BFS를 사용하는 문제이다.

현재 값의 2배, 또는 10배 후 더하기 1 한 값이 되므로, 현재 값보다 작아지는 경우가 없다. 즉, 방문을 확인할 배열이 굳이 필요 없다.

BFS를 수행하며 A가 B가 될 때 수행할 동안 카운트해준 값을 반환한다.

BFS를 수행했음에도 B가 되지 못했다면 -1을 반환한다.

 

📌CODE

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

def solve(n):
    q = deque()
    q.append((n, 1))
    while q:
        now, d = q.popleft()
        if now == B:
            return d
        if 2*now<=B:
            q.append((2*now, d+1))
        plus_one = 10*now+1
        if plus_one<=B:
            q.append((plus_one, d+1))
    return -1

print(solve(A))