[BFS, 경로 복원] 백준 13913. 숨바꼭질 4

숨바꼭질 시리즈의 마지막 문제입니다.

이번에는 단순히 최단 시간만 구하는 것이 아니라, 수빈이가 실제로 이동한 경로를 모두 출력해야 합니다.

---

1. 문제: 백준 13913. 숨바꼭질 4

• 단계: 🥇 골드 4단계
• 주제:
  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색
• 출처: https://www.acmicpc.net/problem/13913

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

---

2. 문제 풀이

최단 시간문제이므로 당연히 BFS로 해결할 수 있습니다.

여기까지는 [숨바꼭질 1]과 동일합니다.

하지만 이번에는 BFS를 하면서 경로도 기록해야 하기 때문에, 각 위치에 도달했을 때 "어디에서 왔는지"를 저장하는 배열이 필요합니다.

핵심: 이전 위치 추적 배열 prev[]

• prev[x]는 x라는 위치에 오기 직전의 위치를 저장합니다.
• BFS가 끝난 뒤, prev[K] → prev[prev[K]] → ... → N까지 거꾸로 추적하면 전체 경로를 복원할 수 있습니다.

구현 코드

from collections import deque
def bfs(N, K):
    queue = deque([N])
    visited = [-1] * 100001
    visited[N] = 0
    prev = [-1] * 100001
    prev[N] = N

    while queue:
        cur_v = queue.popleft()

        for next_v in [cur_v - 1, cur_v + 1, 2 * cur_v]:
            if 0 <= next_v <= 100000 and visited[next_v] == -1:
                visited[next_v] = visited[cur_v] + 1
                queue.append((next_v))
                prev[next_v] = cur_v
    
    return visited[K], prev

def reconstruct(N, K, prev):
    path = []
    curr = K

    while curr!= N:
        path.append(curr)
        curr = prev[curr]
    path.append(N)
    path.reverse()
    
    return path
    
def main():
    N, K = map(int, input().split())

    a, b = bfs(N, K)
    b = reconstruct(N, K, b)
    print(a)
    print(*b)

if __name__ == '__main__':
    main()

---

3. 마무리

이번 문제는 BFS에서 경로 추적 기법까지 자연스럽게 익힐 수 있는 문제였습니다.

실제 코딩 테스트에서 “경로까지 출력하라”는 조건이 나올 수 있으므로 이번 문제를 통해 꼭 익혀두면 좋을 것 같습니다!