[BOJ] 11812 K진 트리

11812번: K진 트리

문제

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

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

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

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

입력

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

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

7 2 3
1 2
2 1
4 7

출력

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

1
1
4

---

어제 공부한 LCA 알고리즘 문제를 더 풀었다. 이 문제는 이진트리가 아니라 어제 감명받았던 테크닉이 들어가 있지는 않지만 매번 풀던 이진트리 문제랑도 달랐다. 

 

이 문제는 완전 이진트리처럼 완전 K진 트리를 만들었을 때 두 노드의 거리를 구하는 문제였다. 노드의 개수가 10^15이라 깊이나 부모를 저장하기 위한 배열을 함부로 만들 수 없는 크기였다. 그래서 이번 문제는 배열은 못 만들고 매번 함수를 호출해서 값을 얻어낸다. 

 

따라서 어제 사용한 부모 위의 부모를 저장하는 테크닉은 사용할 수 없었다. 그냥 하나하나 올라갈 수밖에 없는 문제다. LCA의 기본은 똑같다. 둘의 깊이를 구한 다음에 더 깊은 쪽을 얕은 쪽에 맞춰주고 그다음부터는 같이 올라갔다. 이때 깊이를 구하기 위해서 각 tree level에서의 lower, upper bound를 두고 그 안에 들어오면 값을 반환하는 함수를 사용했다.

 

 

	#include <iostream>
	#include <algorithm>
	using namespace std;
	long long N;
	int K, Q;
	long long get_depth(long long x) {
	long long depth;
	long long left, right;
	if (K == 1) {
	return x;
	}
	if (x == 0) return 0;
	depth = 1;
	left = 1; right = K;
	while (!(left <= x && x <= right)) {
	depth++;
	left = left * K + 1;
	right = right * K + K;
	}
	return depth;
	}
	long long get_parent(long long x) {
	return (x - 1) / K;
	}
	long long get_distance(long long u, long long v) {
	long long depth_u = get_depth(u);
	long long depth_v = get_depth(v);
	long long ret = 0;
	if (depth_u < depth_v) {
	swap(depth_u, depth_v);
	swap(u, v);
	}
	if (K == 1) {
	return depth_u - depth_v;
	}
	long long diff = depth_u - depth_v;
	ret += diff;
	for (long long i = 0; i < diff; i++) {
	u = get_parent(u);
	}
	while (u != v) {
	u = get_parent(u);
	v = get_parent(v);
	ret += 2;
	}
	return ret;
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> K >> Q;
	long long u, v;
	for (int i = 0; i < Q; i++) {
	cin >> u >> v;
	cout << get_distance(u - 1, v - 1) << '\n';
	}
	return 0;
	}

view raw 11812.cpp hosted with ❤ by GitHub

 

후기)

이진트리를 사용하는 자료구조도 많이 다뤄봐서 이진트리는 익숙하지만 이진트리가 아닌 트리를 다루는 데에 익숙하지 않다. 그리고 이 문제처럼 실제로 자료구조를 가지고 있지는 않지만 자료구조를 추상화해서 사용하는 문제도 많이 풀어보지 못했다.