백준알고리즘
[BOJ - 11812] K진 트리
먼지의삶
2020. 4. 26. 09:14
https://www.acmicpc.net/problem/11812
11812번: K진 트리
문제 각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다. 트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다. 아래 그림은 노드 9개로 이루어져 있는 3진 트리이다. 노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를
www.acmicpc.net
아 .. 열심히 작성된 글이 지워져서 처음부터 다시쓴다.
문제 자체의 숫자 범위가 굉장히 크기때문에 일반적인 DFS를 쓰기에는 무리라고 생각했다.
그래서 주어진 값들의 부모를 찾아가서 이들이 만나는 위치를 직접 탐색하고 확인해서
결과를 내는 방법에 착안했다.
규칙성이 한가지 있는데
1을 제외한 어떤 노드라고 하더라도
해당 노드 의 K에 대한 나머지가 1 또는 0 일때는 K로 나눈 몫이 부모 노드가 되고, 그렇지 않다면 몫의 +1 값이 부모 노드가 된다.
이러한 점을 착안해서 쭉 올라간것을 arr을 통해 기록한다.
이때 기록된 배열은 굉장히 특이하게도 역 정렬된 배열이된다.
그 다음 탐색할 숫자를 첫번째 노드가 탐색한것처럼 탐색 하지만, 검색 할때마다 첫번째 값에 대해 부모노드를 기록한 배열에서
이분 탐색을 진행하면서 그 해당 레벨을 찾고 답을 도출한다.