[백준 / Python] 13913번 숨바꼭질 4 | 초코더

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

13913번: 숨바꼭질 4

접근법

숨바꼭질을 참고해주세요.

앞의 문제와 다른부분은 움직이는 경로를 저장해주어야 한다는 점입니다.

path리스트에 이전의 좌표를 저장해둡니다. 그렇다면 path[x]는 x좌표 이전의 좌표에 해당합니다.

그러므로 출력해줄때는 현재의 좌표 x에다가 이전좌표 path[x]를 대입해서 이전좌표들 모두를 p에다가 저장합니다.

 

나의 코드

from collections import deque

def solve(visited,n,k):
    queue=deque()
    queue.append(n)
    while queue:
        x=queue.popleft()

        if x==k:
            #이동하는데 걸리는 최소시간
            print(visited[x])
            #이동한방법은 이동경로를 역순으로 출력
            p=[]
            #p에다가 마지막경로인 x를 넣고
            #x에다가 다시 path에 저장해둔 이전의 좌표 넣기
            #x가 시작점과 같아질때까지 반복
            while x!=n:
                p.append(x)
                x=path[x]
            #while문이 n일때 나가니깐 n은 추가해주기
            p.append(n)
            p.reverse()
            print(' '.join(map(str,p)))
            return

        for nx in (x+1,x-1,x*2):
            if 0<=nx<100001 and visited[nx]==0:
                visited[nx]=visited[x]+1
                #path[다음좌표]=현재좌표
                path[nx]=x
                queue.append(nx)

n,k=map(int,input().split())
visited=[0]*100001
path=[0]*100001
solve(visited,n,k)