[BOJ, C++]#K진 트리, 완전 이진 트리, LCA, 완전 이진 트리의 부모, 완전 이진 트리의 자식

#1. 문제

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

 

---

 

#2. 풀이

 

1. 완전 이진트리

[자료구조]#5_트리

완전 이진트리는 이진트리의 한 종류로, 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있으며, 노드의 삽입 순서는 왼쪽에서 오른쪽 순서입니다.

 

2. LCA(Least Common Acestor)

[BOJ알고리즘, C++]#11437_LCA

LCA는 트리 자료구조의 두 정점의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 다른 말로, 두 노드의 공통 조상 중 깊이가 가장 깊은 노드를 찾는 작업입니다. LCA는 최적활르 위해 Binary Lifting 기법을 활용합니다. Binary Lifting이란, 트리 자료구조의 각 노드의 깊이, 그리고 부모 노드를 2의 승수로 저장하여, 깊이가 깊은 트리 자료구조에서 효율적입니다.

 

3. K진 트리의 부모와 자식 간의 관계!

1. K진 트리에서 현재 노드 n의 이전 노드들의 자식 노드 개수는? K(n-1) + 1
2. 그렇다면, 현재 노드 n의 첫 번째 자식 노드는? K(n-1) + 2
3. 마지막으로, 현재 노드 n의 마지막 자식 노드는? K(n-1) + K + 1 = Kn + 1
4. 첫 번째 자식 노드와 마지막 자식 노드를 통해 부모 노드를 찾는 방법은
   1. K(n-1) + 2 <= n <= Kn + 1
   2. K(n-1) <= n-2
   3. n <= (n+K-2)/K
5. 이를 통해, 각 노드의 부모 노드를 찾는 함수와 깊이 값을 구하고, LCA를 수행합니다.

 

---

 

#3. 코드

@@ -0,0 +1,67 @@
/*
    @링크: https://www.acmicpc.net/problem/11812
*   @문제: K진 트리
*   @설명
        1. LCA 활용
        2. 완전 K진 트리, 부모 노드를 '수학'적으로 찾을 수 있으므로 트리 구성 필요 없다.
        4. 현재 노드로부터 첫 번째 자식 노드와 마지막 자식 노드를 찾는 과정
        5. 위 과정을 통해 얻은 첫 번째 자식 노드와 마지막 자식 노드를 통해 부모 노드를 찾는 과정
*/

typedef long long ll;

ll N;
int K, Q;

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

ll GetParent(ll node)
{
    return (node + K - 2) / K;
}

ll GetDepth(ll node)
{
    if(node == 1) return 0;
    return 1 + GetDepth(GetParent(node));
}

long long LCA(long long x, long long y) {
    while (x != y) {
        if (x < y) y = GetParent(y);
        else x = GetParent(x);
    }
    return x;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K >> Q;

    //@N개의 노드, 완전 K진 트리의 조상 노드, 
    while(Q--)
    {
        ll x,y;
        cin >> x >> y;

        if(K==1)
        {
            cout << abs(x-y) << '\n';
        }
        else
        {
            //@LCA
            ll lca = LCA(x, y);
            //@LCA를 활용한 두 노드 사이의 거리 찾기: dist(root, x) + dist(root, y) - 2 * dist(LCA(x,y));
            cout << GetDepth(x) + GetDepth(y) -2*GetDepth(lca) << '\n';
        }
    }

    return 0;
}

 

---