[백준] 16953 A -> B 파이썬

문제

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

16953번: A → B

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

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

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

입력

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

출력

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

 

 

---

풀이

나는 문제 모음집에서 이 문제를 보았는데, 솔직히 bfs/dfs 카테고리에 없었다면 풀이방법을 좀 고민했을 것 같다.

 

나는 bfs로 풀었다.

 

큐에 a로부터 만들 수 있는 숫자와 count를 넣는다.

큐에서 하나씩 빼며 다시 그 숫자에 2를 곱하거나 1을 오른쪽에 붙인 숫자를 큐에 넣는다

만약 b와 같아지면 count를 출력한다.

 

처음에 visited를 만들어 이미 탐색한 숫자는 다시 탐색하지 않도록 짰었다가 45퍼에서 시간초과가 발생했다.

visited배열에 숫자가 포함되는지 탐색하는 과정의 시간이 더 들었었던 것 같다.

visited를 삭제하고 통과했다.

 

import sys
from collections import deque

a, b = map(int, input().split())

q = deque([(a, 1)])

while q:
    src, t = q.popleft()

    if src == b:
        print(t)
        sys.exit()

    case1 = src * 2
    if case1 <= b:
        q.append((case1, t+1))

    case2 = src*10 + 1
    if case2 <= b:
        q.append((case2, t+1))

print(-1)