[Python] 백준 16953번: A → B

# 문제 내용

백준 16953번: A → B

16953번: A → B

 

# 알고리즘 분류

• 그래프 이론
• 그리디 알고리즘
• 그래프 탐색
• 너비 우선 탐색

 

# 풀이

1. top-down : BFS 이용

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

# a를 b로 바꾸는데 필요한 최소 연산 수 + 1
# 가능한 방법 1 : *2
# 가능한 방법 2 : 1을 수의 가장 오른쪽에 추가
a, b = map(int, input().split())

q = deque()
q.append((a, 1))

while q:
  now, count = q.popleft()

  # 만약 현재 수가 b보다 클 경우 건너뛰기
  if now > b:
    continue
  # 현재 수가 
  if now == b:
    print(count)
    break
    
  # * 2의 경우, 즉 /2의 경우
  q.append((now * 2, count + 1))

  # 1을 더한 경우
  q.append((int(str(now) + "1" ), count + 1))
else:
  print(-1)

 

2. bottom-up 

import sys
input = sys.stdin.readline

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

while b != a:
  result += 1

  # b를 임시 보관
  tmp = b

  # 오른쪽에 1을 추가한 경우: b를 1을 추가하기 전 값으로 변경
  if b % 10 == 1:
    b //= 10
  # 2를 곱한 경우: b를 *2 하기 전 값으로 변경
  elif b % 2 == 0:
    b //= 2

  # 만일 b값이 만들어질 수 없는 값이라면
  # 즉 if문을 아무것도 거치지 않은 경우
  if tmp == b:
    print(-1)
    break
else:
  print(result)

 

# References

https://my-coding-notes.tistory.com/210

[🥈1 / 백준 16953 / 파이썬] A → B