[Java][골드 4] 숨바꼭질 4 - 13913

 

1. 문제 정보

• 문제명: 숨바꼭질 4
• 문제 번호: 13913
• 플랫폼: 백준
• 문제 링크: https://www.acmicpc.net/problem/13913
• 알고리즘 유형: BFS, 경로 추적

 

2. 문제 요약

수빈이 위치 N에서 동생 위치 K까지 가는 최단 시간을 구하고,
동시에 실제 이동 경로를 출력해야 한다.

이동은 아래 3가지가 가능하다.

• x - 1
• x + 1
• 2 * x

 

3. 내 풀이 아이디어

기본은 BFS로 최단 시간을 구하고, parent 배열로 경로를 복원했다.

• dist[next] = dist[cur] + 1로 최단 시간 기록
• parent[next] = cur로 이전 위치 기록
• BFS가 끝난 뒤 K부터 parent를 따라 N까지 역추적
• 역순으로 모였으니 뒤집어서 출력

핵심은 거리 배열(dist) + **부모 배열(parent)**를 같이 쓰는 것이다.

 

4. 풀이 방법

1. visited, dist, parent 배열을 0~100000 범위로 준비한다.
2. 시작점 N을 큐에 넣고 BFS를 시작한다.
3. 다음 위치 x+1, x-1, 2*x를 순회한다.
4. 범위 체크 + 미방문 체크 후 방문 처리한다.
5. 방문 시 거리와 부모를 저장한다.
6. 탐색 후 K -> ... -> N으로 역추적한 뒤 뒤집어 출력한다.
   • 시간복잡도: O(100001)
   • 공간복잡도: O(100001)
   •  

5. 내 코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[100001];
        int[] dist = new int[100001];
        parent = new int[100001];

        parent[n] = n;
        q.add(n);
        visited[n] = true;

        while (!q.isEmpty()) {
            int x = q.poll();
            int[] nextPositions = {x + 1, x - 1, 2 * x};

            for (int nx : nextPositions) {
                if (nx < 0 || nx >= 100001) continue;
                if (visited[nx]) continue;

                visited[nx] = true;
                dist[nx] = dist[x] + 1;
                parent[nx] = x;
                q.add(nx);
            }
        }

        List<Integer> path = new ArrayList<>();
        for (int cur = m; cur != n; cur = parent[cur]) {
            path.add(cur);
        }
        path.add(n);
        Collections.reverse(path);

        System.out.println(dist[m]);
        for (int x : path) {
            System.out.print(x + " ");
        }
    }
}

 

6. 코드 해설

• parent[n] = n:
  시작점 기준을 명확히 해서 역추적 종료 조건을 안정적으로 만든다.
• parent[nx] = x:
  nx에 처음 도달한 최단 경로의 이전 위치를 저장한다.
• for (cur = m; cur != n; cur = parent[cur]):
  목적지에서 시작점까지 따라 올라가며 경로를 복원한다.
• Collections.reverse(path):
  역방향 경로를 정방향으로 변환한다.

 

7. 회고

• 이번 문제는 최단 시간 자체보다 경로를 저장하고 출력하는 과정이 더 까다로웠다.
  dist만으로는 경로 복원이 불가능해서 parent를 함께 관리해야 했다.
  다음에는 K를 찾는 즉시 BFS를 종료하는 방식도 적용해볼 예정이다.