[BOJ/백준] 16953. A -> B (Python)

🔎 문제

🔗 백준 16953. A -> B

💡 풀이

DFS(재귀)로 풀면 메모리 초과가 난다. 재귀호출을 하게되면 스택에 메모리를 쌓게되는데 이때 재귀호출을 너무 많이 해서 그런 것 같다.

실패한 DFS 코드

import sys
sys.setrecursionlimit(10**7)
    
def dfs(a, b, cur, count):
  global MIN
  if cur == b:
    MIN = min(MIN, count)
    MIN += 1
    return
  elif cur > b:
    return
  else:
    dfs(a, b, cur * 2, count + 1)
    dfs(a, b, int(str(cur) + '1'), count + 1)

a, b = map(int, input().split())
MIN = sys.maxsize
dfs(a, b, a, 0)

print(MIN)

이건 ‘최소’를 구하는 문제이므로(2178. 미로탐색 포스트 참고) BFS가 적절하다. 자세한 소스코드는 아래에 첨부했다.

📃 소스코드

from collections import deque

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

Q = deque([(a, 1)])
while Q:
    n, count = Q.popleft()
    if n == b:
        MIN = count
        break
    if n * 2 <= b:
        Q.append((n * 2, count + 1))
    if int(str(n) + '1') <= b:
        Q.append((int(str(n) + '1'), count + 1))

print(MIN)

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️