[BOJ/백준 11812/C++] K진 트리

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

 

[ 문 제 ]

- 각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다.

- 트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다.

- 아래 그림은 노드 9개로 이루어져 있는 3진 트리이다.

- 노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 프로그램을 작성하시오.

 

[ 문 제 조 건 ]

- 첫째 줄에 N (1 ≤ N ≤ 10^15)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다.

- 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y ≤ N, x ≠ y)

 

- 총 Q개의 줄을 출력한다. 각 줄에는 입력으로 주어진 두 노드 사이의 거리를 출력한다.

 

[ 문 제 풀 이 ]

문제의 핵심은 질문으로 들어온 두 정점(x,y)에 대해 최소 공통 조상을 찾고, 각 노드의 최소 공통 조상까지의 거리를 더하면 되는 문제다.

 

하지만 이번 문제는 존재할 수 있는 노드들의 갯수가 10^15개로 노드의 수가 엄청나다.

 

하지만 문제에서 주어지는 트리는 항상 K보다 작거나 같은 수의 자식을 가지되, 완전 이진 트리와 같이 왼쪽 부터 채워지는 트리이다.

• 완전 이진 트리(Complete Binary Tree)는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드들은 왼쪽부터 순서대로 채워진 이진 트리입니다. 즉, 트리의 각 레벨이 가능한 한 왼쪽부터 빈 공간 없이 노드로 채워져 있어야 합니다

하지만 이 문제는 이진트리가 아니라 K진 트리다.

 

그렇다면 생각해 볼 수 있는 방법이 하나 있다. 완전 이진 트리에서 하나의 정점의 부모노드의 번호를 알아내는 방법은 매우 간단하다. (현재 노드의 번호 / 2 = 부모 노드의 번호) 

 

이 아이디어를 이용해 K진트리에서 적용되도록 일반화 시키면, P(K진트리에서 임의의 한 노드이 번호)의 부모노드의 번호는 " (P + ( K - 2 )) / K "가 된다.(몫만 따짐)

 

예를들어 K=3일때, 3번 노드의 자식 노드의 번호들은 8,9,10이다. 이때 역으로 8,9,10노드에 위의 식을 대입하면 3 노드 모두 3이 나오게 된다.

 

이런 방식으로 두 정점에서 부모노드를 찾아가면서 값이 같아지는 순간이 최소 공통 조상의 번호가 되고, 연산한 총 횟수가 두 정점간의 거리가 된다.

 

이때 a, b 두 값 중 큰 값이 위의 식을 적용하여 연산을 진행한다.

 

[ 소스 코드 ]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll N, K, Q;

	cin >> N >> K >> Q;
	
	for (ll i = 0; i < Q; i++)
	{
		ll a, b;
		cin >> a >> b;
		ll interval = (K-2);
		ll cnt = 0;
		if (K == 1)
		{
			cnt = abs(a - b);
		}
		else
		{
			while (a != b)
			{
				if (a < b)
				{
					b = (b + interval) / K;
				}
				else
				{
					a = (a + interval) / K;
				}
				cnt++;
			}
		}
		cout << cnt << "\n";

	}
	
}

 

그리고 만약 K=1인 일자형 트리의 경우는 단순하게 두 노드 번호의 차가 정답이 된다.

 

굳