February 16, 2023

13913번: 숨바꼭질 4

문제 요약

• 점 N(0 ≤ N ≤ 100,00)에서 점 K(0 ≤ K ≤ 100,000)까지 아래의 연산을 최소한으로 거쳐 이동하는 최소 연산 수와 경로
  • X - 1
  • X + 1
  • X * 2

풀이

from collections import deque

N, K = map(int, input().split())
visited = [-1] * 200_001

def bfs():
    global result

    q = deque()

    q.append((N, 0, N))

    while (q):
        node, time, prev_node = q.popleft()

        if (visited[node] != -1):
            continue

        visited[node] = prev_node

        if (node == K):
            print(time)
            return

        if (node < K and node + 1 <= 200_000 and visited[node + 1] == -1):
            q.append((node + 1, time + 1, node))

        if (node - 1 >= 0 and visited[node - 1] == -1):
            q.append((node - 1, time + 1, node))

        if (node < K and node * 2 <= 200_000 and visited[node * 2] == -1):
            q.append((node * 2, time + 1, node))

bfs()

idx = K
result = [K]

while (idx != N):
    result.append(visited[idx])
    idx = visited[idx]

result.reverse()

print(*result)

• BFS 경로를 저장해두고, 출력