백준 16953 A->B | python | bfs

문제

링크

풀이

문제에서 얘기한대로 정수 a를 b로 바꾸려고 할 때 가능한 연산은 아래 두 가지이다.

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

이 문제는 bfs를 bottom-up (a에서 b로 가기 위해 계속 값을 더해감) 형식으로 풀이하면 쉽게 답을 찾을 수 있다.

먼저 큐를 준비한 뒤 정수 a를 0으로 초기화된 depth와 함께 튜플 형태로 넣어준다. (= q.append((A,depth)) ) 여기서 depth는 연산 횟수를 의미하며 이를 통해 현재 값의 연산 횟수를 알 수 있다.

이후 while문을 돌며 큐에 원소가 존재한다면 원소를 pop한다.

만약 pop한 원소가 b와 같다면, a에서부터 b까지의 연산을 가장 빠르게 즉, 최소 연산으로 마친 것이므로 간주할 수 있기에 break로 멈춘 뒤 연산 횟수를 출력한다.

pop한 원소가 b가 아니라면, 아직 원소 b가 되기 위한 연산 과정이 남아있다는 뜻이므로 현재 원소에서 1) 2를 곱한 경우 와 2) 1의 수를 가장 오른쪽에 추가하는 경우 를 큐에 삽입한다. 이 때 연산 개수를 의미하는 depth를 1 증가시켜 함께 삽입하는 것을 잊으면 안된다.

만약 큐에 원소가 모두 비었는데도 답을 출력하지 못했다면 -1을 출력한다.

import sys
from collections import deque

input = sys.stdin.readline

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


def bfs():
    q = deque()
    depth = 1
    result = 0
    q.append((a, depth))
    while q:
        n, depth = q.popleft()
        if n == b:
            result = depth
            break
        depth += 1
        # 2를 곱하는 경우
        cur_1 = n * 2
        if cur_1 < b:
            q.append((cur_1, depth))
        elif cur_1 == b:
            result = depth
            break
        # 1의 수를 가장 오른쪽에 추가하는 경우
        cur_2 = n * 10 + 1
        if cur_2 < b:
            q.append((cur_2, depth))
        elif cur_2 == b:
            result = depth
            break
    return result


result = bfs()
if not result:
    print(-1)
else:
    print(result)