[백준] 16953번 문제 (A → B) 파이썬(Python) 풀이

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

16953번: A → B

from collections import deque
import sys

a, b = map(int, input().split())
q = deque()
q.append([a, 0])

while q:
    num, depth = q.popleft()
    if num == b:
        print(depth + 1)
        sys.exit(0)
    if b >= num * 2:
        q.append([num * 2, depth + 1])
    if b >= int(str(num) + str(1)):
        q.append([int(str(num) + str(1)), depth + 1])

print(-1)

bfs를 통해 풀었다.

입력으로 주어진 a부터 시작하여 두가지 연산을 모두 해보며 탐색을 하게된다.

탐색 중 a가 b와 일치하는 순간 depth를 출력해주고,

탐색이 끝나면 a와 b가 일치하는 경우가 없기 때문에 -1을 출력해준다.