[Python] 13913번 숨바꼭질 4

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

체감 난이도: ★★★★☆

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

#dfs
def bfs(n):
    MAX=100001 #메모리초과 방지
    prev=[-1]*MAX #이전 경로 저장
    dist=[0]*MAX #시간 count
    prev[n]=100001 #현재 위치 저장

    queue=deque([n])
    while queue:
        x=queue.popleft()

        #만약 동생 위치 도착하면
        if x==K:
            break

        for nx in (x-1,x+1,x*2):
            if 0<=nx<MAX: 
                if prev[nx]==-1: #이전에 방문한 적 없다면
                    queue.append(nx)
                    prev[nx]=x #다음 경로에 현재 경로 위치 값 저장
                    dist[nx]=dist[x]+1

    #현재 위치 인덱스에서 이전 경로 역추적
    path=[]
    idx=K
    while idx!=100001: #현재 위치로 돌아오기까지
        path.append(idx)
        idx=prev[idx]

    #4.출력
    print(dist[x])
    path=list(reversed(path))
    for p in path:
        print(p,end=' ')


#1.입력 #2.자료형 정의
N,K=map(int,input().split())

#3.함수
bfs(N)

 

메모리 초과와 시간 초과를 둘 다 생각했어야해서 까다로운 문제였다.