백준 11812 K진트리

부모 노드 번호와 자식 노드 번호 사이의 관계를 식으로 만들 수 있느냐가 해당 문제의 핵심이다. 이외에는 간단한 분기문으로 풀 수 있다.
노드의 개수가 $10^{15}$ 개 이므로, 수학적 공식 활용 외에 다른 알고리즘으로 간선의 개수를 세려고 하면 무조건 시간 초과가 난다.

(1) 부모 - 자식 노드 번호 공식 구하기


"부모" = ("자식" - 2)/K + 1;

문제에서는 루트가 1부터 시작하지만, 공식을 쉽게 이해를 위해서 먼저 루트 번호가 0번이라고 생각해 보겠다. 먼저 K = 3 인 3진 트리가 입력으로 주어졌다고 해보자.

깊이를 h라고 하고, cnt(h)는 깊이 당 노드가 꽉 차 있을 때 노드의 수라고 해보자.
K = 3에서, cnt(0) = 1, cnt(1) = 3, cnt(3) = 9 임이 보인다.
따라서 cnt(h) =

K^{h}

임을 알 수 있다.

여기서 중요한 점은 하나의 노드마다 정확히 K개의 노드만 가진다는 것이다 따라서 특정 깊이의 노드 번호를 K로 나누면 그 몫이 부모의 노드 번호가 된다. 이때 자식 노드의 시작이 0번 부터가 아닌, 1번부터 시작했으므로 나누는 대상에서 -1을 해줘야 한다. 따라서 루트가 0번인 K진 트리에서 부모 - 자식 간의 공식은 다음과 같다.


"부모" = ("자식" - 1 ) / K

이제 위의 공식을 루트가 1인 K진 트리에 대한 공식으로 바꿔야 한다. 이때 필요한 건 클리크 조정이다.

루트가 1부터 시작되므로 전체에 공식에 1을 더한다.
또한 자식의 최초 번호도 2부터 시작되므로 정확한 나눗셈을 위해서 -1 을 -2로 바꿔줘야 한다.
따라서 최종 공식은 다음과 같다.


"부모" = ("자식" - 2 ) / K + 1

(2) 공통 조상 구하기

노드 a,b가 있을 때, a의 노드 번호가 b 보다 크다면, a의 깊이 레벨이 b보다 깊거나 같다는 뜻이다. 깊이가 깊을 가능성이 있는 노드에 대하여 위의 공식을 통해 부모를 구한다. 이후 해당 노드를 부모로 갱신한다.

이 과정을 a와 b가 하나의 노드로 만날 때까지 반복한다.

(3) 예외 처리 K = 1일 때

K = 1일 때는 트리가 선형일 것이므로, 부모 - 자식 공식으로 노드를 줄여봤자 시간복잡도가 O(logN)이 아닌 O(N)이 될 것이다. 이 경우 위의 공식으로 구하면 오히려 시간 초과가 난다.

K = 1 일 경우는 두 노드 번호의 차이의 절대값이 두 노드 사이의 거리가 되므로, 위의 공식 사용 없이 바로 두 노드간의 차의 절대값을 구하여 출력하면 된다.

(4) 시간복잡도 분석 ⏳

자식에서 부모를 찾아서 깊이가 한 단계 낮아질 때마다 확인해야할 노드의 수가 K배씩 줄어든다. 따라서 문제에서 주어진 자식이 x라고 쳤을 때, x가 루트까지 가는데 필요한 연산횟수는

\log_x{k}

이다.

문제에서 Q = 100,000, K = 1,000 로 주어졌다. 여기서 K는 작을수록 계산 횟수가 늘어나지만, K= 1 은 예외처리 했으므로 K = 2일 때를 최악의 경우로 보자. 또한 모든 쿼리문에서 주어진 두 개의 노드가

10^{15}

깊이에서 시작하여 루트 노드에서 처음으로 만난다고 해보자.

그렇다면 시간 복잡도는 다음과 같다.

O(100,000 \times \log_2{10^{15}})

log_2{10^{15}}=49.82892...

이므로 시간 초과에 해당하지 않는다.

3. 코드 🌐


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

public class Main {
    static long N;
    static int K, Q;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Long.parseLong(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        StringBuilder ans = new StringBuilder();
        for(int i = 0; i < Q; i++){
            st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            if(K == 1){
                ans.append(Math.abs(a-b)).append("\\n");
                continue;
            }
            int cnt = 0;
            while (a != b){
                if(a > b){
                    a = find_parents(a);
                }
                else if (a < b){
                    b = find_parents(b);
                }
                cnt++;
            }
            ans.append(cnt).append("\\n");
        }
        System.out.println(ans);
    }

    public static long find_parents(long child){
        if(child == 1) return 1;
        return (child-2)/K + 1;
    }
}