이 튜토리얼에서는 N-ary(다진) 트리의 깊이를 구하는 방법을 알아보겠습니다.
N-ary 트리란?
N-ary 트리는 각 노드가 최대 n개의 자식 노드를 가질 수 있는 트리 구조입니다. 이진 트리(binary tree)가 자식을 최대 2개까지만 가질 수 있다면, N-ary 트리는 그 개수가 n으로 일반화된 형태입니다.
우리는 이 N-ary 트리의 깊이(depth), 즉 루트 노드에서 가장 깊은 리프 노드까지의 거리를 구해야 합니다. 각 노드의 자식들은 vector를 사용하여 저장합니다.
문제 해결 접근 방식
재귀(recursion)를 활용하면 트리의 깊이를 간단하게 계산할 수 있습니다. 단계별로 살펴보겠습니다.
- 더미 데이터로 트리를 초기화합니다.
- N-ary 트리의 깊이를 구하는 재귀 함수를 작성합니다.
- 트리의 최대 깊이를 저장할 변수를 초기화합니다.
- 각 노드의 모든 자식을 순회(iterate)하면서 다음을 수행합니다.
- 최대 깊이는 현재 최대 깊이와 해당 자식 노드의 깊이 중 더 큰 값입니다.
- 최대 깊이 변수를 maxDepth라고 하면, 재귀 호출문은 maxDepth = max(maxDepth, findDepthOfTree(*children)) 형태가 됩니다.
- 최종적인 트리의 최대 깊이는 maxDepth + 1입니다.
- 구한 트리의 최대 깊이를 출력합니다.
C++ 구현 예제
전체 코드를 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
vector<Node *> child;
};
Node *newNode(int data) {
Node *temp = new Node;
temp->data = data;
return temp;
}
int findDepthOfTree(struct Node *node) {
if (node == NULL) {
return 0;
}
int maxDepth = 0;
for (vector<Node*>::iterator it = node->child.begin(); it != node->child.end(); it++) {
maxDepth = max(maxDepth, findDepthOfTree(*it));
}
return maxDepth + 1;
}
int main() {
Node *root = newNode(1);
root->child.push_back(newNode(2));
root->child.push_back(newNode(3));
root->child.push_back(newNode(4));
root->child[2]->child.push_back(newNode(1));
root->child[2]->child.push_back(newNode(2));
root->child[2]->child.push_back(newNode(3));
root->child[2]->child.push_back(newNode(4));
cout << findDepthOfTree(root) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
3
코드 설명
예제에서 루트 노드에는 3개의 자식 노드가 있고, 세 번째 자식 노드에는 다시 4개의 자식 노드가 있습니다. 따라서 루트에서 리프 노드까지 총 3단계에 걸쳐 내려가므로 결과값은 3이 됩니다.
재귀 함수 findDepthOfTree는 노드가 NULL일 경우 0을 반환하고, 그렇지 않으면 모든 자식 노드를 순회하며 각 자식의 깊이를 재귀적으로 계산한 뒤, 그중 최댓값에 1을 더해 반환합니다. 이 방식의 시간 복잡도는 O(n)으로, 트리의 모든 노드를 한 번씩만 방문하므로 매우 효율적입니다.
마무리
지금까지 C++에서 vector와 재귀 함수를 활용해 N-ary 트리의 깊이를 구하는 방법을 알아보았습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.