b13913. 순간이동 4

 

 

📌 자바(Java)로 푸는 숨바꼭질 4 - 백준 13913🧍‍♂️➡️🧍‍♀️

 

최소 시간 + 이동 경로까지 출력하는 BFS 문제!

 

🔎 문제 개요

 

백준 13913번 - 숨바꼭질 4는

정수 N(수빈이 위치)에서 K(동생 위치)까지

다음 세 가지 연산으로 이동해 최소 시간을 구하는 문제입니다.

 

• X - 1
• X + 1
• X * 2

 

뿐만 아니라,

✔ 최단 시간과 함께

✔ 그때의 이동 경로를 정확히 출력해야 합니다!

 

---

💡 예제 입력

5 17

 

💡 예제 출력

4
5 10 9 18 17

 

 

---

🛠 알고리즘 접근 방식

 

이 문제는 전형적인 최단 거리 탐색 → BFS 문제입니다.

하지만 경로 추적까지 해야 하므로,

✔ 이동 이전 위치를 기록하는 prev[] 배열을 활용해야 합니다.

 

---

🔹 Java 코드 설명

📌 Node 클래스

static class Node {
    int position;
    int time;
    ...
}

✔ 현재 위치와 걸린 시간을 함께 저장하는 클래스

 

 

📌 BFS 로직

static int bfs() {
    Queue<Node> queue = new ArrayDeque<>();
    queue.offer(new Node(start, 0));
    visited[start] = true;

    while (!queue.isEmpty()) {
        Node current = queue.poll();

        if (current.position == end) {
            return current.time;
        }

        for (int next : new int[]{current.position - 1, current.position + 1, current.position * 2}) {
            if (next >= 0 && next < MAX && !visited[next]) {
                visited[next] = true;
                prev[next] = current.position;
                queue.offer(new Node(next, current.time + 1));
            }
        }
    }
    return -1;
}

✔ visited[]로 중복 방문 방지

✔ prev[next] = current.position로 경로 저장

✔ 도착하면 current.time을 반환

 

 

📌 경로 출력 로직

static void printPath() {
    Deque<Integer> path = new ArrayDeque<>();
    for (int at = end; at != -1; at = prev[at]) {
        path.push(at);
    }

    StringBuilder sb = new StringBuilder();
    while (!path.isEmpty()) {
        sb.append(path.pop()).append(" ");
    }
    System.out.println(sb.toString().trim());
}

✔ prev[]를 거슬러 올라가며 stack에 저장

✔ stack을 사용해 순서대로 출력

 

---

🏆 정리

✅ 핵심 포인트

 

• BFS는 최단 거리 탐색에 적합
• 경로 복원은 prev[] 배열을 통해
• O(N) 시간 안에 정답 경로 추적 가능