[백준 11812번] K진 트리 (C++)

문제링크 : https://www.acmicpc.net/problem/11812

11812번: K진 트리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int K, Q;
ll N, x, y;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> K >> Q;
    while(Q--)
    {
        cin >> x >> y;
        ll cnt = 0;

        while(x!=y && K!=1) //서로 만날 때까지 (조상노드가 같을 때까지)
        {
            if(x>y) x=(x-2)/K+1; //큰 값 기준으로 부모노드 찾기
            else y=(y-2)/K+1;
            cnt++;
        }
        cout << (K==1 ? abs(x-y) : cnt) << "\n"; //K=1일때 예외처리
    }
    return 0;
}

최소 공통 조상을 응용한 문제이다.

먼저 N의 범위가 매우 크기에 (10^15) 자료형 선언에 주의해야 한다.

그리고 K진 트리의 부모 노드 찾는 것에 다음과 같은 공식이 존재한다.

P=(C-2)/K+1
P=부모노드 / C=자식노드 / K=차수

이를 이용하여 입력받은 노드 x, y에 대해 서로 부모노드를 계속해서 찾아가면서 만나는 순간을 찾아주면 된다.

x, y 중 큰 값을 기준으로 먼저 부모노드를 찾으며, 서로의 부모노드가 같아질때까지이를 반복하는데 매 탐색마다 카운팅을 해준다.

서로 부모노드를 만나는 순간까지 저장된 카운트가 해당 문제에서 구하고자하는 두 노드 사이의 거리가 된다.

예제 : 7 2 3 / 4 7
    1
   2 3
 4 5 6 7
 
y = 7 -> 3 (cnt = 1)
x = 4 -> 2 (cnt = 2)
y = 3 -> 1 (cnt = 3)
x = 2 -> 1 (cnt = 4 / x==y)

그리고 추가적으로 주의해야할 점이 있는데 K==1인 경우이다.

K==1인 경우 사용했던 공식이 P=C-1이 된다. (P=(C-2/1)+1)

이 경우 복잡도가 O(C)가 되어 시간초과가 발생할 수 있다.

따라서 K=1인 경우 트리가 단순 일직선의 형태를 나타나게 되므로 abs(x-y)의 거리를 구해주면 된다.

ex) 5 1 / 1 5
1
2
3
4
5

abs(1-5) = 4