[백준] 13913번(숨바꼭질 4)

백준 13913번

최종 제출 코드

from collections import deque

n, k = map(int, input().split())
queue = deque()
result = deque()
visited = [-1] * 100001
parent = [0] * 100001

start_node = n
queue.append(n)
visited[n] = 0

# n->k 의 최소 depth와 각 노드의 부모를 리스트에 저장
def bfs():

  while queue:

    value = queue.popleft()

    if value == k:
      return visited[value]

    values = [value-1, value+1, value*2]
    
    for i in values:
      if i >= 0 and i <= 100000 and visited[i] == -1:
        queue.append(i)
        visited[i] = visited[value]+1
        parent[i] = value

depth = bfs()

result.append(k)
for i in range(depth):
  parent_node = parent[result[0]]
  result.appendleft(parent_node)

print(depth)
print(*result)

◼️ 깊이를 체크하는 visited 리스트와 parent 리스트를 활용

• bfs를 활용하여 노드를 탐색
• queue에 노드가 업데이트 될 때마다 visited, parent 리스트의 값 또한 업데이트
• bfs()에서 n->k의 최소 깊이를 return하면, k부터 노드의 부모를 추적하여 result의 맨 앞에 값을 붙여준다