[백준] 25418번 정수 a를 k로 만들기 파이썬

문제

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

입력

첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

제한

1 ≤ A < K ≤ 1,000,000

예제 입력 1

5 10

예제 출력 1

1

제출 답안

from collections import deque
import sys

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

a, k = map(int, input().split())
visited = [False] * (k + 1)


def bfs():
    q = deque([(a, 0)])
    visited[a] = True
    while q:
        node, cnt = q.popleft()
        if node == k:
            return cnt
        plus = node + 1
        if plus <= k:
            if not visited[plus]:
                visited[plus] = True
                q.append((plus, cnt + 1))
        double = node * 2
        if double <= k:
            if not visited[double]:
                visited[double] = True
                q.append((double, cnt + 1))


print(bfs())