문제

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

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

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

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

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

예제 입력 1
5 17
예제 출력 1
4
5 10 9 18 17

예제 입력 2
5 17
예제 출력 2
4
5 4 8 16 17

---

접근

숨바꼭질 시리즈는 진짜 유명한... 근본 BFS 문제들인데, 그런 거에 비해 내 이해도가 많이 부족한 것 같아서 이번에 제대로 한 번 풀어보기로 했다.

숨바꼭질 문제를 BFS로 접근해야 하는 이유는 현재 위치에서 가능한 이동(X-1, X+1, X*2)를 모두 탐색해본 후 초수를 늘려가야 하기 때문이다.
1초동안 가능한 모든 이동, 2초동안 가능한 모든 이동, 3초동안 가능한 모든 이동.... 이런 순으로 탐색하다 보면 K에 도달했을 때의 초수가 당연히 K에 도달 가능한 최소 시간임이 보장된다.

하지만 이건 너무 당연한 얘기이고... 숨바꼭질 4에서 핵심은, 단순히 가장 빠른 시간을 출력하는 게 아니라 어떻게 이동해야 해야 하는지도 기록해서 함께 출력해야 된다는 것이다.

구현

초기 시도

당연히 더 메모리 효율적인 방법이 있으리라고 생각은 했지만 내가 몰라서... 처음에는 큐에 지나온 경로를 담은 리스트를 넣는 무식한 방법으로 구현을 했었다.

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

class Main {
    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());

        Set<Integer> visited = new HashSet<>();
        Queue<List<Integer>> q = new LinkedList<>();
        List<Integer> path = new ArrayList<>();
        path.add(N);
        q.offer(path);
        while (!q.isEmpty()) {
            List<Integer> currPath = q.poll();
            int currLocation = currPath.get(currPath.size() - 1);

            if (currLocation == K) {
                printList(currPath);
                return;
            }

            if (currLocation - 1 >= 0 && !visited.contains(currLocation - 1)) {
                visited.add(currLocation - 1);
                List<Integer> minus = new ArrayList<>();
                minus.addAll(currPath);
                minus.add(currLocation - 1);
                q.offer(minus);
            }
            if (currLocation < K) {
                if (!visited.contains(currLocation * 2) {
                    visited.add(currLocation * 2);
                    List<Integer> multiply = new ArrayList<>(currPath);
                    multiply.add(currLocation * 2);
                    q.offer(multiply);
                }
                if (!visited.contains(currLocation + 1)) {
                    visited.add(currLocation + 1);
                    List<Integer> plus = new ArrayList<>(currPath);
                    plus.add(currLocation + 1);
                    q.offer(plus);
                }
            }
        }
    }

    private static void printList(List<Integer> list) {
        StringBuilder sb = new StringBuilder();
        sb.append(list.size() - 1).append("\n");
        for (int location : list) {
            sb.append(location).append(" ");
        }
        System.out.println(sb.toString());
    }
}

그런데 이렇게 구현했을 때 메모리 초과는 예상했지만,,, 뜻밖에도 시간 초과가 났다.

출력의 길이가 작은 경우에는 큰 문제가 없다. 하지만 입력이 100000 0처럼 주어졌다면 뒤로밖에 이동할 수 없는데, 100000에서 0까지 1씩 감소시키며 모든 수를 출력하는 데 너무 오래 걸리는 것이었다.

내 처음 구현에서 비효율적이었던 부분은 다음과 같다.
1. 입력이 N > K라면, N에서 K에 도달할 때까지 1씩 뒤로만 가는 것이 반드시 최적이다.
난 처음에 1씩 뒤로 가다가 N < K가 된 후 앞으로 가는 경우도 있지 않나? 하고 깊게 생각을 안 했는데, 조금만 생각해보면 뒤로 갔다가 다시 앞으로 간다는 것 자체가 비효율적인 이동이라는 것을 알 수 있다.
따라서, 입력이 N > K라면 BFS를 수행할 필요가 없이 N에서부터 1씩 감소시키며 K까지 출력하면 된다. 앞서 언급한 입력인 100000 0에서 발생하는 시간 초과도 이렇게 해결했다.
2. 각 탐색마다의 경로를 리스트에 저장할 필요가 없다.
다음 위치에 도달할 때마다 별도의 배열에 현재 위치의 정보를 저장해둔 후, 이를 역추적하면 모든 탐색에 대한 경로를 각각 저장하지 않아도 되었다. BFS이기 때문에 다음 위치에 가장 먼저 도달케 한 현재 위치가 다음 위치에 가장 빠르게 도달할 수 있는 위치임이 보장되는 것.

최적화

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

class Main {
    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());

        if (N >= K) {
            StringBuilder sb = new StringBuilder();
            sb.append(N - K).append("\n");
            for (int i = N; i >= K; i--) {
                sb.append(i).append(" ");
            }
            System.out.println(sb.toString());
            return;
        }

        boolean[] isVisited = new boolean[200001];
        int[] prev = new int[200001];
        Queue<Integer> q = new LinkedList<>();
        isVisited[N] = true;
        prev[N] = -1;
        q.offer(N);
        while (!q.isEmpty()) {
            int curr = q.poll();

            if (curr == K) {
                printPath(prev, N, K);
                return;
            }

            if (curr - 1 >= 0 && !isVisited[curr - 1]) {
                isVisited[curr - 1] = true;
                prev[curr - 1] = curr;
                q.offer(curr - 1);
            }
            if (curr + 1 < 200001 && !isVisited[curr + 1]) {
                isVisited[curr + 1] = true;
                prev[curr + 1] = curr;
                q.offer(curr + 1);
            }
            if (curr * 2 < 200001 && !isVisited[curr * 2]) {
                isVisited[curr * 2] = true;
                prev[curr * 2] = curr;
                q.offer(curr * 2);
            }
        }
    }

    private static void printPath(int[] prev, int start, int end) {
        List<Integer> path = new ArrayList<>();
        path.add(end);
        for (int i = end; prev[i] != start; i = prev[i]) {
            path.add(prev[i]);
        }
        path.add(start);
        
        StringBuilder sb = new StringBuilder();
        sb.append(path.size() - 1).append("\n");
        for (int i = path.size() - 1; i >= 0; i--) {
            sb.append(path.get(i)).append(" ");
        }
        System.out.println(sb.toString());
    }
}