[백준/Python] (S2) A → B - 16953

Baekjoon Online Judge의 16953번 A → B 문제의 Python풀이입니다.

16953번: A → B

🧠문제 분석

이 문제는 주어진 정수 A를 B로 변환하는 데 필요한 최소 연산 횟수를 찾는 것입니다.

가능한 연산은 정수에 2를 곱한다, 정수의 가장 오른쪽에 1을 추가한다.
주어진 범위는 A < B이며, A와 B 모두 1과 10^9 사이의 정수입니다. 만약 A를 B로 변환할 수 없으면 -1을 출력해야 합니다.

🤔문제 풀이

이 문제의 해결 방법은 너비 우선 탐색(BFS) 알고리즘을 사용하는 것입니다. 주어진 문제는 정수 A를 B로 변환하는 최소한의 연산 횟수를 찾는 것으로, 가능한 두 가지 연산은 2를 곱하거나 숫자의 가장 오른쪽에 1을 추가하는 것입니다.

해결 접근 방식
큐 초기화: 먼저, deque(이중 끝 큐)를 사용하여 탐색할 숫자들의 큐를 초기화합니다. 큐에는 숫자와 그 숫자에 도달하기 위해 수행한 연산 횟수의 쌍을 저장합니다. 초기에는 B와 연산 횟수 0을 큐에 넣습니다.

BFS 탐색: 큐가 비어있지 않는 동안, 큐에서 원소를 하나씩 꺼내어 탐색을 진행합니다.

만약 현재 숫자가 A와 같다면, 필요한 연산 횟수(큐에서 꺼낸 숫자의 연산 횟수)에 1을 더해 출력하고 탐색을 종료합니다.
만약 현재 숫자가 A보다 작다면, 이 숫자는 더 이상 유용하지 않으므로 무시합니다.

가능한 연산 수행:
만약 현재 숫자가 2로 나누어 떨어진다면(짝수라면), 2로 나눈 값을 큐에 추가합니다. 이때 연산 횟수를 1 증가시켜 함께 저장합니다.
만약 현재 숫자의 마지막 자리가 1이라면, 마지막 자리 1을 제거한 수(즉, 10으로 나눈 몫)를 큐에 추가합니다. 마찬가지로 연산 횟수는 1 증가시켜 저장합니다.

변환 불가능 판단:
만약 큐가 비었는데도 A를 B로 변환하는 것이 불가능하다면(즉, BFS 탐색이 끝나도록 A에 도달하지 못했다면), -1을 출력합니다.

💻코드

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

queue = deque([(B, 0)])  # (현재 값, 연산 횟수)
while queue:
    current, steps = queue.popleft()

    if current == A:
        print(steps + 1)  # 연산 횟수에 1을 더해서 반환
        break
    if current < A:
        continue

    # 2로 나누는 연산
    if current % 2 == 0:
        queue.append((current // 2, steps + 1))

    # 오른쪽에 1을 제거하는 연산
    if str(current).endswith("1"):
        queue.append((int(str(current)[:-1]), steps + 1))

# 변환할 수 없는 경우
else:
    print(-1)