[백준] 16953번 A → B 해설 및 풀이 (Python)

백준 16953번 A → B

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

---

문제

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

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

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

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

---

문제 유형

 

그래프 이론

그리디 알고리즘

그래프 탐색

너비 우선 탐색

 

풀이 방법 도출

 

BFS(너비 우선 탐색) 방식으로 탐색을 진행하면서 AAA에서 BBB로 변환하는 최단 경로를 찾는다.

 

1. 큐(queue)에 (현재 숫자, 연산 횟수) 를 저장합니다.
2. BFS를 수행하면서 다음 두 가지 연산을 실행합니다. 첫 번째로 현재 숫자 × 2, 두 번째로 현재 숫자 × 10 + 1를 실행합니다.
3. 만약 목표 숫자 BBB 에 도달하면, 연산 횟수 +1 을 반환합니다.
4. 목표 숫자보다 커지는 경우 탐색을 종료합니다.
5. BFS 탐색이 끝나도 BBB 에 도달하지 못하면 -1을 반환합니다.

시간 복잡도

• 탐색 : O(log B)
• 중복 확인 : O(1)
• 큐의 삽입 및 삭제 연산 : O(1)
• 최종 시간 복잡도 : O(log B)

---

핵심 코드 삽입 및 설명

 

import sys
from collections import deque


def bfs(start, end):
    queue = deque([(start, 1)])  # ​큐 초기화
    visited = set()  # visited 중복 탐색 방지

    while queue:
        num, count = queue.popleft()

        if num == end:
            return count  # 연산 횟수 반환

        # 2를 곱하는 연산
        next_num = num * 2
        if next_num <= end and next_num not in visited:
            queue.append((next_num, count + 1))
            visited.add(next_num)

        # 1을 추가하는 연산
        next_num = num * 10 + 1
        if next_num <= end and next_num not in visited:
            queue.append((next_num, count + 1))
            visited.add(next_num)

    return -1  # 만들 수 없는 경우

# 입력 받기
input = sys.stdin.readline().strip().split()
a, b = int(input[0]), int(input[1])

# 결과 출력
print(bfs(a, b))