[acmicpc] 13913. 숨바꼭질 4(python)

리스트에 방문했던 위치를 계속 누적했을 경우 메모리초과가 나와서,

딕셔너리를 통해 해당 위치의 전 위치를 저장하는 방법으로 구현하였습니다.

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

N,K=map(int,input().split())
visit=[0]*100001
q=deque()
dicts=defaultdict(int)
q.append(N)
while q:
    num=q.popleft()
    if num==K:
        print(visit[num])
        answer=[]
        while num!=N:
            answer.append(num)
            num=dicts[num]
        answer.append(N)
        answer.reverse()
        print(' '.join(map(str,answer)))
        break
    for tmp in (num+1,num-1,num*2):
        if 0<=tmp<=100000 and visit[tmp]==0:
            dicts[tmp] = num
            visit[tmp] = visit[num] + 1
            q.append(tmp)

---

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

13913번: 숨바꼭질 4