[BOJ | 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을 출력한다.

 

풀이

from collections import deque

A, B = map(int, input().split())

def bfs():
    queue = deque()
    queue.append((A, 1))
    visited = set()
    visited.add(A)

    while queue:
        num, cnt = queue.popleft()
        if num == B:
            return cnt
        for next_num in (num * 2, num * 10 + 1):
            if next_num <= B and next_num not in visited:
                visited.add(next_num)
                queue.append((next_num, cnt + 1))
    return -1

print(bfs())

 

전형적인 최단 거리 탐색 문제이며, BFS를 사용하여 풀었다.

- 현재 숫자에서 바꿀 수 있는 경우는 X*2, X*10+1 두가지

- BFS로 탐색하면 가장 먼저 도착한 경로가 최솟값

- 큐에 숫자와 연산 횟수를 삽입하며(연산의 최솟값에 1을 더한 값을 출력해야 하므로 연산 횟수의 초깃값을 1로 설정), 연산으로 바꿀 수 있는 경우의 수에 대해 계속해서 탐색함

- 숫자가 B와 같아지면 cnt를 반환

- while문이 끝남 == cnt를 return하지 않음 이므로 불가능한 값이기 때문에 -1을 반환