[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를 두고 그 안에 들어오면 값을 반환하는 함수를 사용했다.

 

 

 

후기)

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