[파이썬] 백준 1697 숨바꼭질

# 십만일개의 원소를 갖는 리스트를 생성해서 해결함. 십만개 정도 리스트는 메모리 초과가 안나서 신기함
# d[k] 가 0이 아니면 방문을 한 것이기 때문에 답을 출력해준다.
 
import sys
from collections import deque
 
 
N,k = list(map(int,sys.stdin.readline().split(" ")))
 
 
# bfs -> 메모리 초과(temp 리스트 때문)  -> 제거했는데도 메모리 초과
 
d = [0]*100001
d[N] = 1
 
queue = deque()
queue.append(N)
 
temp = [ ]
 
while queue:
 
 
 
    x = queue.popleft()
 
    if d[k]!=0:
        print(d[k]-1)        
        break
 
    if 0<=x-1 and d[x-1]==0:
        d[x-1] = d[x] + 1
        queue.append(x-1)
 
    if x+1<=100000 and d[x+1]==0:
        d[x+1] = d[x] +1
        queue.append(x+1)
 
    if 2*x <= 100000 and d[2*x]==0:
        d[2*x] = d[x] + 1
        queue.append(x*2)
 
 
'''
# 리스트를 업데이트 하기 -> 시간 초과 날듯? -> 메모리 초과남
 
a = []
a.append(N)
 
while True:
 
    if K in a:
        print(answer)
        break
 
 
    temp = [ ]
 
    for i in range(0,len(a)):
        for j in range(0,3):
 
            if j==0:
                if a[i]+1<=100000:
                    temp.append(a[i]+1)
 
            if j==1:
                if a[i]-1>=0:
                    temp.append(a[i]-1)
 
            if j==2:
                if a[i]*2<=2*K:
                    temp.append(a[i]*2)
 
 
 
    a = temp
 
    answer += 1
 
'''