백준 알고리즘 16953: A->B (Python)

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

16953번: A → B

---

문제 해결을 위한 과정

이 문제의 경우 bfs를 이용하면 해결할 수 있는 문제였습니다. 다만, visited 배열을 만들게 되면 10^9 * 4B = 4000MB 이므로 배열을 생성해서는 안됩니다. 따라서 배열을 생성하지 않고 단순하게 큐에 삽입이 될 수가 b와 같은지를 확인하면 됩니다. 

---

소스코드

from collections import deque

a, b = map(int, input().split())
q = deque()
q.append(a)
ans = int(1e9)
cnt = 1

while q:
  length = len(q)
  for _ in range(length):
    v = q.popleft()
    for i in range(2):
      if i == 0:
        nv = 2 * v
      else:
        nv = int(str(v) + str(1))
      if nv == b:
        ans = cnt
        break
      if nv <= b:
        q.append(nv)
  cnt += 1

if ans == int(1e9):
  print(-1)
else:
  print(ans + 1)