[Python]동적계획법과 최단거리 역추적 백준 13913

   문제

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

이전에 풀어봤던 문제이다.

현재위치에서 -1 +1 *2의 위치를 큐에 넣고 큐를 이용해 동생의 위치가 나올때까지 BFS를

 실행하면된다.

이번 문제는 발자취를 구해야한다.

역으로 +1,-1,*2의 위치에서 도착위치보다 1작은 시간만큼 소요했다면 그곳을 들렸다고

 볼수있다 .이런식으로 도착지에서 출발지가 나올때 까지 반복해주면된다.

배열의 역순 출력을 다른방법을 사용해봤다.아주 간단하게 작성할수 있었다.

from collections import deque
 
N,K=map(int,input().split())
if N>=K:
    print(N-K)
    #시작지가 더큰경우 1씩 줄여가며 출력해주면된다
    for i in range(N,K-1,-1):
        print(i,end=" ")
else:
    check=[0 for _ in range(K+2)]
 
    q=deque()
    q.append(N)
    check[N]=1
    while q:
        x=q.popleft()
        if x==K:
            time=check[x]-1
            break
        if x+1<=K+1 and check[x+1]==0:#x+1로 걷기
            check[x+1]=check[x]+1
            q.append(x+1)
        if x-1>=0 and check[x-1]==0:#x-1로 걷기
            check[x-1]=check[x]+1
            q.append(x-1)
        if x*2<=K+1 and check[2*x]==0:#순간이동
            check[x*2]=check[x]+1
            q.append(x*2)
 
    print(time)
 
 
    #역으로 추적해준다
    result=[K]
    x=K
 
    while x!=N:
        if x%2==0 and check[x//2]== check[x]-1:#절반이 지금지점보다 1작다면
            result.append(x//2)
            x//=2
        elif check[x-1]==check[x]-1:#1 작은곳에서 왓다면
            result.append(x-1)
            x-=1
        elif check[x+1]==check[x]-1:#1 큰곳에서 왓다면
            result.append(x+1)
            x+=1
 
    print(*result[::-1])