문제 접근

문제를 잘 생각해보자. 만약 방법의 가짓수를 구하지 말라고 했다면? 그냥 일반적인 BFS로 끝났을 것이다.
하지만, 이 문제는 방법의 가짓수를 구해야한다.
이게 좀 골치아파질 수 있으나, 잘 생각해보자... a라는 위치에 도달하는 가장 빠른 시간은 정해져있다. 그냥 N부터 BFS로 방문여부처리하면서 가장 먼저 A가 나왔을 때의 트리 레벨L이다.

그렇다면, a가 L 이후에 등장한 경우의 경로가 N->K로 가는 최단 경로일 수 있는가? 아니다.
그렇다면, a -> b 라는 노드로 이동할 때를 생각해보자. 만약 a라는 노드로 레벨L까지 도달할 수 있는 가짓수가 X개이면, b까지 L+1 레벨로 도달할 수 있는 가짓수는 일단 X개 확보다.

레벨L+1에 b까지 도달할 수 있는 경우가 a->b밖에 없는가? 아닐 수 있다. 그렇다면 b까지 레벨 L+1에 도달할 수 있는 모든 가짓수는 b까지 도달했던 부모들의 가짓수들의 합이다.

또 여기서 우리는 생각해봐야 한다.
그렇다면, 일반적인 BFS 탐색처럼 매번 노드를 방문할 때 마다 자기 형제들이 그 노드에 방문 못하게 막으면 안된다...
즉, 트리 구조에서 한 레벨이 끝날 때마다 그동안 나왔던 모든 새로운 노드들을 처리해야한다는 것이다.

이를 위해 나는 다음과 같은 전략을 세웠다.

• 큐가 빌때까지는 일단 계속 음수로 값을 저장한다. (조건식에 안걸리기 위해. 0보다 크면 윗 레벨에서 나온 이미 나온 값인거임)
• 큐가 비면, 이번 레벨에서 방문한 새로운 노드들을 대상으로 양수로 값을 뒤집어서 해당 노드까지 가야하는데 걸린 횟수를 제대로 저장한다.
• 그리고 집합을 비우고, 레벨을 하나 키워서 다음 레벨 탐색을 준비한다.
• 참고로, N 시작 지점은 가짓수가 0이지만, 이걸 그냥 더해버리면 영원히 isVisited가 0이라서 이 경우만 특별히 1로 더해준다. 삼항조건식이 있는 이유다.

문제 풀이

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

public class Main {
    
    static int K;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        if (K <= N) {
            System.out.println(N - K);
            System.out.println(1);
            return;
        }

        // 형제들끼리는 동일한 곳에 도달할 수 있음. 즉 먼저 먹더라도 먹은척하지마!

        int[] isVisited = new int[15_0002];
        LinkedList<Integer> q = new LinkedList<>();
        q.add(N);
        isVisited[N] = 0;
        int curLevel = 0; // 현재 0 레벨 처리 중

        Set<Integer> curLevelSets = new HashSet();
        while (!q.isEmpty()) {
            int curN = q.poll();

            int nextN = curN + 1;
            if (isIn(nextN) && isVisited[nextN] <= 0 && nextN != N) {
                isVisited[nextN] -= (isVisited[curN] == 0 ? 1 : isVisited[curN]);
                curLevelSets.add(nextN);
            }

            nextN = curN - 1;
            if (isIn(nextN) && isVisited[nextN] <= 0 && nextN != N) {
                isVisited[nextN] -= (isVisited[curN] == 0 ? 1 : isVisited[curN]);
                curLevelSets.add(nextN);
            }

            nextN = curN * 2;
            if (isIn(nextN) && isVisited[nextN] <= 0 && nextN != N) {
                isVisited[nextN] -= (isVisited[curN] == 0 ? 1 : isVisited[curN]);
                curLevelSets.add(nextN);
            }

            if (q.isEmpty()) {
                for (int n : curLevelSets) {
                    isVisited[n] = -isVisited[n]; // 음으로 세던거 뒤집기
                    q.add(n);
                }
                curLevel++;

                if (curLevelSets.contains(K)) {
                    break;
                }
                curLevelSets.clear();
            }
        }

        System.out.println(curLevel);
        System.out.println(isVisited[K]);
    }

    private static boolean isIn(int n) {
        return n >= 0 && n <= 15_0001;
    }
}

오랜만에 풀어서 그런가 새롭다... 골드4가 원래 이렇게 어려웠나.. 2시간 걸린 것 같다 후우.. 다시 화이팅해보자