[백준] 13913번 : 숨바꼭질 4 - JAVA [자바]

https://www.acmicpc.net/problem/13913

bfs 알고리즘 문제이다.

시간을 구하는 것은 [백준] 1697번 : 숨바꼭질 - JAVA [자바]을 풀었으면 구할 수 있을 것이다.

이제 방문 순서를 구하는 것이 문제이다.

N 에서 갈 수 있는 방향은 3 가지이므로 순서를 구하는 것이 어렵다.

하지만 반대로 나의 부모는 하나 밖에 없다.
즉, 시간 배열은 시간이 가장 적게 걸리는 방법일 때 업데이트 되며 이때의 부모는 하나이다.

그러므로 시간 배열과 같은 부모 배열을 만들어서 N 에서 출발해서 K 에 도착 하는 최단 시간은 시간 배열[K]에 저장하고 K의 부모는 부모 배열 [K]에 저장한다.

그 후 목적지 K 부터 N까지 부모 배열을 역순으로 출력해야 하기 때문에 K의 부모부터 stack에 push하여 N까지 넣고 stack을 돌아가면서 pop 하여 출력하면 된다.

public class bj13913 {

    public static int N, K;
    public static boolean[] visited = new boolean[100001];
    public static int[] time = new int[100001];
    public static int[] parent = new int[100001];
    public static Queue<Integer> queue = new LinkedList<>();
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line = br.readLine();
        String[] split = line.split(" ");

        N = Integer.parseInt(split[0]);
        K = Integer.parseInt(split[1]);

        bfs(N);

        bw.write(time[K] + "\n");

        // 순서대로 구하기 위해 stack 에 담았다가 다시 pop
        Stack<Integer> stack = new Stack<>();
        stack.push(K);
        int index = K;

        while (index != N) {
            stack.push(parent[index]);
            index = parent[index];
        }

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

        bw.write(sb + "");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void bfs(int start) {
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            start = queue.poll();
            visited[start] = true;
            int moveLeft = start - 1;
            int moveRight = start + 1;
            int teleport = start * 2;
            if (teleport <= 100000) {
                // 방문 안했으면 값 업데이트
                if (!visited[teleport]) {
                    queue.add(teleport);
                    time[teleport] = time[start] + 1;
                    visited[teleport] = true;
                    parent[teleport] = start;
                } else {
                    // 방문했었지만
                    // 지금 방법이 더 빠른 경우
                    if (time[teleport] > time[start] + 1) {
                        queue.add(teleport);
                        time[teleport] = time[start] + 1;
                        parent[teleport] = start;
                    }
                }
            }
            if (moveLeft >= 0){
                // 방문 안했으면 값 업데이트
                if (!visited[moveLeft]) {
                    queue.add(moveLeft);
                    time[moveLeft] = time[start] + 1;
                    visited[moveLeft] = true;
                    parent[moveLeft] = start;
                } else {
                    // 지금 방법이 더 빠른 경우
                    if (time[moveLeft] > time[start] + 1) {
                        queue.add(moveLeft);
                        time[moveLeft] = time[start] + 1;
                        parent[moveLeft] = start;
                    }
                }
            }
            if (moveRight <= 100000) {
                // 방문 안했으면 값 업데이트
                if (!visited[moveRight]) {
                    queue.add(moveRight);
                    time[moveRight] = time[start] + 1;
                    visited[moveRight] = true;
                    parent[moveRight] = start;
                } else {
                    // 지금 방법이 더 빠른 경우
                    if (time[moveRight] > time[start] + 1) {
                        queue.add(moveRight);
                        time[moveRight] = time[start] + 1;
                        parent[moveRight] = start;
                    }
                }
            }
        }
    }

}