백준 | A → B

백준 A → B

import sys


a, b = map(int, sys.stdin.readline().strip().split())

# leaves: 현재 깊이(depth)에서 b가 될 가능성이 있는 값들
leaves = [a]

# min_op: a를 b로 바꾸기 위한 연산의 최소 횟수
min_op = 0
while True:
    temp = []

    for leaf in leaves:
        # 메모리 초과를 방지하기 위해 b 이하의 값(주어진 연산으로 b를 만들 가능성이 있는 값)만 남긴다.
        new_leaf = leaf * 2
        if new_leaf <= b:
            temp.append(new_leaf)
        
        new_leaf = int(str(leaf) + '1')
        if new_leaf <= b:
            temp.append(new_leaf)

    leaves = temp
    min_op += 1

    # leaves가 비어 있다면, b를 만들 수 없는 것이므로 -1을 출력한다.
    if not leaves:
        print(-1)
        break

    # leaves에 b가 포함되어 있다면, 조건에 따라 min_op + 1을 출력한다.
    if b in leaves:
        print(min_op + 1)
        break

a를 b로 바꾸기 위한 최소 연산 횟수를 구하는 문제이므로, BFS로 접근해도 된다.

주어진 숫자(a)가 정의된 두 연산에 의해 트리와 같은 계층 구조로 확장되며, BFS는 단계별로 이 구조를 탐색하며 최단 경로를 보장하기 때문이다.

import sys
from collections import deque


a, b = map(int, sys.stdin.readline().strip().split())

# BFS를 위한 queue를 (현재 값, 연산 횟수) 형태로 초기화한다.
queue = deque([(a, 1)])

while queue:
    current, steps = queue.popleft()

    if current == b:
        print(steps)
        break

    if current * 2 <= b:
        queue.append((current * 2, steps + 1))
    if int(str(current) + '1') <= b:
        queue.append((int(str(current) + '1'), steps + 1))
else:
    print(-1)