[백준] 13913번 숨바꼭질 4 ★★

💡문제접근

• N에서 K로 가는 최단 시간과 해당 경로를 출력해야 하는 문제다.
• 이전 지점이 어디인지를 저장하는 배열을 만들어 같이 출력한다.

💡코드(메모리 : 48276KB, 시간 : 128ms)

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

N, K = map(int, input().strip().split())
move = [0] * 100001         # 이동 경로
visited = [0] * 100001      # 걸린 시간

def BFS(n):
    queue = deque()
    queue.append(n)
    while queue:
        v = queue.popleft()
        if v == K:
            print(visited[v])
            ans = []
            while v != N:
                ans.append(v)
                v = move[v]
            ans.append(N)
            ans.reverse()
            print(' '.join(map(str, ans)))
            return
        for x in [v-1,v+1,v*2]:
            if 0 <= x <= 100000 and not visited[x]:
                visited[x] = visited[v] + 1
                queue.append(x)
                move[x] = v

BFS(N)

💡소요시간 : 42m