[탐색/BFS] 백준 13913 숨바꼭질 4 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

13913번: 숨바꼭질 4

 

 

 

2. 문제 풀이

수빈이는 1초에 +1, -1, *2만큼 이동할 수 있습니다. X 지점에서 Y로 이동하는 최소 시간을 구해야 합니다.

 

2022.02.24 - [Algorithm] - [탐색/BFS] 백준 1697 숨바꼭질 - Python

[탐색/BFS] 백준 1697 숨바꼭질 - Python

 기존 숨바꼭질 문제에서 '경로 추적'이 추가된 문제입니다. 경로는 parents 리스트를 추가해서 추적할 수 있습니다.

 

 

 

3. 코드

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

N, K = map(int, input().split())  #출발 / 도착
dist = [0] * 100001  # 최대 0부터 100000까지의 지점까지 걸리는 횟수 기록
parents = [0] * 100001  # 경로 추적

# BFS 탐색
queue = deque()
queue.append(N)  # 시작점

# 큐가 빌 때까지 탐색
while queue:
    x = queue.popleft()
    # 도착지점이라면 탐색 종료
    if x == K:
        print(dist[x])  # 최적 경로
        path = []
        for _ in range(dist[x]+1):
            path.append(x)
            x = parents[x]
        print(" ".join(map(str, path[::-1])))
        break

    # x에서 -1 또는 +1 또는 *2 탐색
    for nextX in (x+1, x-1, 2*x):
        # 0~100000지점 내이고, 방문하지 않았거나 동일한 탐색횟수를 가졌으면 탐색
        if 0 <= nextX <= 100000 and not dist[nextX]:
            dist[nextX] = dist[x] + 1  # 방문하고 횟수 1늘림
            parents[nextX] = x
            queue.append(nextX)  # 큐에 추가

 parents에 부모 노드(이전 노드)를 저장해두고, 거슬러 올라가면서 추적합니다. 만약 최적 경로가 1 -> 3 -> 5라고 합시다. 그러면 노드 5의 부모 노드는 '3'이고, 노드 3의 부모 노드는 '1'입니다. 이를 역순으로 재배열하면 1, 3, 5 최적 경로가 됩니다.

 

2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

[Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

 경로를 역추적하는 방법은 다익스트라 알고리즘을 설명하면서, 소개한 적이 있습니다. 더 자세한 설명은 위 글을 참조해주세요.