[백준 16953번] A -> B - python

문제 링크

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

16953번: A → B

풀이 

- bfs 문제 

- 큐에 숫자와 횟수 추가 

   2를 곱한 수가 b보다 크지 않으면 큐에 추가, 횟수 +1 

   1를 오른쪽에 추가한 수가 b보다 크지 않으면 큐에 추가, 횟수 + 1

- 큐에서 꺼낸 숫자가 b와 같으면 횟수 return  

from collections import deque 

def bfs(a):
  q = deque()
  q.append((a,1))
  
  while q:
    x, cnt = q.popleft()

    if x == b:
      return cnt 

    if x*2 <= b :
      q.append((x*2, cnt + 1))
    
    # 스트링으로 바꿔 오른쪽에 '1'을 추가한 후 다시 int로 바꿔줌 
    tmp = int(str(x) + '1')
    if tmp <= b :
      q.append((tmp,cnt+1))

  return -1 

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

print(bfs(a))