BOJ 13913 숨바꼭질4(Python 3)

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

문제 난이도에 비해 정답 비율이 높은 문제다.

이 문제를 다시 풀다보니 그동안 숨바꼭질 문제에서 굳이 필요하지 않은 코드가 있다는 것을 알고 수정하였다.(중복 확인 코드가 사실 필요 없다.)

이동 과정을 저장하는 방법은 2차원 리스트를 만들어서 D[nx][0]은 시간에 대한 값, D[nx][1]은 이전에 있던 좌표인 x를 저장하여 나중에 K를 구할 때 D[nx][1]을 보고 역추적 할 수 있도록 만들었다.

N은 10, K는 80이라고 예시를 들어보면 10 -> 20 -> 40 -> 80 이라는 이동경로가 있을 때, D[80][1]엔 40이 저장되어 있을 것이고, D[40][1]은 20, D[20][1]은 10이 저장되어 있으니까 이 값을 전부 저장하여 출력하면 된다.

코드확인

from collections import deque
Max=10**5+1
N,K=map(int,input().split())
D=[[-1]*2 for _ in range(Max)]
D[N][0]=0
q=deque([N])
T=[K]
z=K
while q:
    x=q.popleft()
    for nx in [x+1,x-1,2*x]:
        if 0<=nx<Max and D[nx][0]==-1:
            q.append(nx)
            D[nx][0]=D[x][0]+1
            D[nx][1]=x
while D[z][1]!=-1:
    T.append(D[z][1])
    z=D[z][1]
print(D[K][0])
print(*reversed(T))