13913: 숨바꼭질 4

• bfs의 path를 구하기 위해서, path라는 이름의 list를 생성하여, queue에 node를 append 할 때마다 path에 이전 노드를 저장해줌 (자식 노드에 부모 노드를 저장)
• 이런 식으로 저장된 연결 관계를 이용하여 K부터 시작해 역순으로 최단 경로의 path를 찾아줌

import sys
from collections import deque

def bfs(N, K):
    queue = deque([]); queue.append(N)


    while queue:
        curr = queue.popleft()

        if curr == K:
            print(visit[curr])
            return

        if 0 <= curr-1 <= 100000 and curr-1 != N and visit[curr - 1] == 0:
            queue.append(curr - 1); visit[curr-1] = visit[curr] + 1
            path[curr-1] = curr #이전 step 저장
        if 0 <= curr+1 <= 100000 and curr+1 != N and visit[curr + 1] == 0:
            queue.append(curr + 1); visit[curr+1] = visit[curr] + 1
            path[curr+1] = curr #이전 step 저장
        if 0 <= curr*2 <= 100000 and curr*2 != N and visit[curr * 2] == 0:
            queue.append(curr * 2); visit[curr*2] = visit[curr] + 1
            path[curr*2] = curr #이전 step 저장

   
N, K = map(int, input().split(' '))

visit = [0] * (100000+1)
path = [0] * (100000+1)
bfs(N, K)

answer = []; curr = K; answer.append(curr)
for i in range(visit[K]):
    before = path[curr]; answer.append(before)
    curr = before
for i in range(len(answer)-1, -1, -1):
    print(answer[i], end=" ")

• path의 원소들은 각각 부모 노드를 저장하고 있음 (vist[nx] == 0일 때만 queue에 append + path update -> override 안됨)
• bfs를 순회하면서 curr == K일 때 return 하므로 K에 도착했을 때 이후로 override 되는 일은 없음