[백준/파이썬] 16953번: A → B

문제

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

풀이

• A를 B로 바꾸는데 필요한 연산의 최솟값 출력
  • 2를 곱한다.
  • 1을 수의 가장 오른쪽에 추가한다.

A를 2를 곱하거나 1을 A의 가장 오른쪽에 추가하여 B가 되는지 탐색하는 문제입니다.

저는 BFS를 사용하여 문제를 해결했습니다.

def bfs():
    queue = deque([(a, 1)])

queue에 초기 숫자 A와 연산 횟수 1을 추가합니다.

    while queue:
        node, cnt = queue.popleft()
        

queue에서 숫자와 연산 횟수를 추출해 연산을 시작합니다.

        if node * 2 <= b:
            queue.append((node * 2, cnt + 1))
            
        if int(str(node) + '1') <= b:
            queue.append((int(str(node) + '1'), cnt + 1))
    
    return -1

node에 연산한 값이 b보다 작거나 같다면 (연산한 값, 연산 횟수 + 1)을 queue에 추가

        if node == b:
            return cnt

만약 node와 결괏값인 b가 같다면 연산 횟수 리턴

코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    queue = deque([(a, 1)])
    
    while queue:
        node, cnt = queue.popleft()
        
        if node == b:
            return cnt
        
        if node * 2 <= b:
            queue.append((node * 2, cnt + 1))
            
        if int(str(node) + '1') <= b:
            queue.append((int(str(node) + '1'), cnt + 1))
    
    return -1

if __name__ == "__main__":
    a,b = map(int,input().split())
    print(bfs())