💻 백준 16953: A→B

문제 소개 🧐

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

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

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

입력 📝

  • 첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

출력 📤

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

제한 ❌

  • 2초, 512MB

첫 번째 시도: BFS (실패) 👊

Idea

A에서 B로 가는 경우의 수를 모두 탐색하기보다, B에서 A로 역으로 연산을 수행하는 것이 더 효율적일 것이라 생각했다. B에 대해 가능한 역연산은 다음과 같다.

  1. 2로 나눈다.
  2. 오른쪽의 1을 제거한다.

B에서부터 시작하여 A가 될 때까지 BFS(너비 우선 탐색)를 적용했다. 메모리 초과를 피하기 위해 visited 배열 없이, (현재 값, 연산 횟수)를 튜플로 큐에 저장하여 탐색을 진행했다.

Code

import sys
from collections import deque

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

q = deque()
q.append((b, 0))

while q:
    num, cnt = q.popleft()

    if num % 10 == 1:
        next_num = num // 10
        if next_num == a:
            print(cnt + 2)
            exit()
        q.append((next_num, cnt + 1))

    # 짝수 여부 확인 없이 2로 나누는 로직 오류
    next_num = num // 2
    if next_num == a:
        print(cnt + 2)
        exit()
    q.append((next_num, cnt + 1))

print(-1)

Result

  • 실패 ⏰
  • num이 홀수일 때도 2로 나누는 연산을 시도하는 로직 오류가 있었다. 또한, q가 비었을 때 루프가 정상적으로 종료되지 않는 문제가 있었다.

두 번째 시도: BFS (로직 수정) ✨

Idea

첫 번째 시도의 문제점을 수정했다.

  • 2로 나누는 연산은 num이 짝수일 때만 수행하도록 if num % 2 == 0: 조건을 추가했다.
  • 큐(q)가 비었을 때 while 루프가 정상적으로 종료되고, 최종적으로 -1이 출력되도록 로직을 보완했다.
  • 시작 연산 횟수를 1로 설정하여 출력 시 cnt만으로 최종 연산 횟수를 계산하도록 수정했다.

Code

import sys
from collections import deque

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

q = deque()
q.append((b, 1)) # 시작 연산 횟수를 1로 설정

while q:
    num, cnt = q.popleft()

    if num == a:
        print(cnt)
        exit()

    if num % 10 == 1:
        next_num = num // 10
        if next_num >= a:
            q.append((next_num, cnt + 1))

    if num % 2 == 0:
        next_num = num // 2
        if next_num >= a:
            q.append((next_num, cnt + 1))

print(-1)

Result

  • 성공! ✅
  • B에서 A로 가는 역연산을 통해 탐색 공간을 줄이고, BFS를 적용하여 최단 경로(최소 연산)를 효율적으로 찾을 수 있었다.

개선할 부분 🤔

  • 현재 코드는 BFS를 사용하여 모든 가능한 경우를 탐색하지만, 사실 이 문제는 그리디한 접근으로도 해결할 수 있다.
  • B에서 역연산을 할 때, 2로 나누어떨어지면 2로 나누고, 그렇지 않고 끝이 1이면 1을 떼는 방식으로 하나의 경로만 탐색해도 정답을 찾을 수 있다. 이 경우 코드가 더 간결해질 수 있다.