BOJ 11812

K진 트리

문제출처

문제 해석

• 총 N개의 노드로 이루어져 있는 K진트리가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 문제입니다.

설계(10)

• N의 범위가 <=10^15이므로 K진트리를 구성해서 푸는 문제는 아닌 것을 알 수 있습니다.
• 문제를 풀기에 앞서 K진트리의 특성을 이해해야 했습니다.
• 이진 트리에서 특정 노드(node)의 자식은 node2 , node2+1임을 바로 알 수 있습니다.
• 반대로 자식이 부모를 알기위해서는 node+(2-2)/2를 하면 알 수 있습니다.
• 따라서 K진트리에서 node의 부모를 알고싶으면 (node+K-2)/K를 하면 됩니다.
• 두번째로 K진트리에서 두 노드가 a < b이면, depth[a] <= depth[b] 인것을 알 수 있습니다.(왼쪽부터 순차적으로 채워지기 때문입니다.)
• 위 두가지 특성을 이용해서 최소 공통 조상을 찾을 수가 있고, 이는 두 노드간 거리가 됩니다.
• 깊이가 더 깊은 노드(a < b이면 b)를 해당 노드의 부모로 갱신하는 것을 a와 b가 같아질 때까지 반복해주면 거리를 구할 수 있습니다.
• 여기서 예외로 K가 1인 범위 또한 주어질 가능성이 있는데, 1진트리는 그냥 1부터 N까지 일렬로 나열된 트리이기 때문에 a와 b의 거리를 구하려면 최악의 경우 O(10^15)가 나와 시간초과가 나올 것입니다.
• K=1일 때 a와 b의 차이값이 곧 거리이기 때문에 예외처리로 값을 내줘야 합니다.

구현(20)

코드

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll N;
int K,Q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K >> Q;
    while (Q--){
        ll a,b;
        cin >> a >> b;
        //1진트리 예외 처리
        if (K == 1){
            cout << abs(a-b)<<"\n";
            continue;
        }
        int ans = 0;
        while (a!=b){
            if (a<b){
                b = (b+K-2)/K;
            }
            else if (a > b){
                a = (a+K-2)/K;
            }
            ans++;
        }
        cout << ans <<"\n";
    }
    return 0;
}

디버깅

제출결과

• 52ms

마무리

• LCA의 개념과 K진트리의 특성을 알아야 두 노드간의 거리를 구할 수 있는 문제였습니다. LCA 알고리즘 관련문제를 풀어보기 전에 풀어보기에 좋은 문제인 것 같습니다.