[BaekJoon] 13913번 - 숨바꼭질 4 [Java][C++]

문제 링크

---

1. 문제 풀이

BaekJoon 1697번 - 숨바꼭질 문제에서 최단 시간과 최단 경로까지 구해야 하는 문제로 최단 경로를 구하기 위해 이전에 어떤 위치에서 왔는지 저장하는 prev 배열을 활용했다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

    static final int MAX = 100_000;

    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 k = Integer.parseInt(st.nextToken());

        System.out.println(bfs(n, k));
    }

    static String bfs(int n, int k) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(n);

        boolean[] visited = new boolean[1 + MAX];
        visited[n] = true;

        int dist = 0;

        int[] prev = new int[1 + MAX];
        Arrays.fill(prev, -1);

        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                int node = q.poll();
                if (node == k) return traceback(dist, k, prev);

                int next1 = node - 1;
                if (next1 >= 0 && !visited[next1]) {
                    q.offer(next1);
                    visited[next1] = true;
                    prev[next1] = node;
                }

                int next2 = node + 1;
                if (next2 <= MAX && !visited[next2]) {
                    q.offer(next2);
                    visited[next2] = true;
                    prev[next2] = node;
                }

                int next3 = node * 2;
                if (next3 <= MAX && !visited[next3]) {
                    q.offer(next3);
                    visited[next3] = true;
                    prev[next3] = node;
                }
            }

            dist++;
        }

        return null;
    }

    static String traceback(int dist, int k, int[] prev) {
        StringBuilder sb = new StringBuilder();
        Deque<Integer> stack = new ArrayDeque<>();

        sb.append(dist).append("\n");

        int pos = k;
        while (pos != -1) {
            stack.push(pos);
            pos = prev[pos];
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }

        return sb.toString();
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX = 100000;
bool visited[1 + MAX];
int prv[1 + MAX];

void traceback(int dist, int k) {
    vector<int> v;

    int pos = k;
    while (pos != -1) {
        v.push_back(pos);
        pos = prv[pos];
    }

    reverse(v.begin(), v.end());

    cout << dist << '\n';

    for (int x : v) {
        cout << x << ' ';
    }
}

void bfs(int n, int k) {
    queue<int> q;
    q.push(n);

    visited[n] = true;

    memset(prv, -1, sizeof(prv));

    int dist = 0;

    while (!q.empty()) {
        int size = q.size();

        while (size-- > 0) {
            int node = q.front();
            q.pop();

            if (node == k) {
                traceback(dist, k);
                return;
            }

            int next1 = node - 1;
            if (next1 >= 0 && !visited[next1]) {
                q.push(next1);
                visited[next1] = true;
                prv[next1] = node;
            }

            int next2 = node + 1;
            if (next2 <= MAX && !visited[next2]) {
                q.push(next2);
                visited[next2] = true;
                prv[next2] = node;
            }

            int next3 = node * 2;
            if (next3 <= MAX && !visited[next3]) {
                q.push(next3);
                visited[next3] = true;
                prv[next3] = node;
            }
        }

        dist++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    bfs(n, k);
}

---