[백준] 13913번 숨바꼭질4

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

계속 메모리 초과가 났는데, 이전에 지나온 위치를 계산할 때 무한 반복되는 구간이 있어 

-1로 초기화해줄 필요가 있었다

path[N]=-1로 출발위치만 초기화해주면 된다

from collections import deque
from collections import defaultdict
N, K = map(int, input().split())
MAX_SIZE = 100001

q = deque()
q.append(N)
path=defaultdict(int)
check=[-1]* MAX_SIZE
check[N]=0
path[N]=-1
while q:
    x = q.popleft()
    if x==K:
        break
    for y in [x - 1, x + 1,2*x]:
        if 0 <= y < MAX_SIZE:
            if check[y]==-1:
                check[y]=check[x]+1
                path[y]=x
                q.append(y)

print(check[K])
answer=deque()
answer.appendleft(K)
x=path[K]
while x!=-1:
    answer.appendleft(x)
    x=path[x]

print(' '.join(map(str,answer)))