개요
이 튜토리얼에서는 N-진 트리(n-ary tree)에서 모든 노드의 하위 트리에 속한 리프 노드(leaf node)의 개수를 구하는 프로그램을 작성해 보겠습니다.
N-진 트리가 주어졌을 때, 각 노드를 루트로 하는 하위 트리에 포함된 리프 노드의 수를 계산해야 합니다. 먼저 예시를 통해 문제를 살펴보겠습니다.
입력
N = 8 tree = [[2, 3], [], [4, 5, 6], [7, 8], [], [], [], []]
출력
1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1
위 입력은 1번 노드가 2번, 3번 노드를 자식으로 가지며, 3번 노드는 4, 5, 6번 노드를, 4번 노드는 7, 8번 노드를 자식으로 갖는 트리 구조를 나타냅니다. 리프 노드인 2, 5, 6, 7, 8번 노드의 리프 개수는 1이고, 4번 노드는 자신의 하위 트리에 2개의 리프(7, 8번)를 가집니다. 같은 방식으로 3번 노드는 4개, 루트인 1번 노드는 총 5개의 리프 노드를 갖게 됩니다.
알고리즘
- 원하는 형태로 N-진 트리를 초기화합니다.
- DFS(깊이 우선 탐색)를 사용하여 트리를 순회합니다.
- 각 노드의 리프 노드 개수를 저장할 배열을 유지합니다.
- 재귀적으로 DFS를 호출한 후, 자식 노드의 리프 개수를 부모 노드의 값에 더해 나갑니다.
- 순회가 끝나면 모든 노드와 해당 노드의 리프 노드 개수를 출력합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
void insertNode(int x, int y, vector<int> tree[]) {
tree[x].push_back(y);
}
void DFS(int node, int leaf[], int visited[], vector<int> tree[]) {
leaf[node] = 0;
visited[node] = 1;
for (auto it : tree[node]) {
if (!visited[it]) {
DFS(it, leaf, visited, tree);
leaf[node] += leaf[it];
}
}
if (!tree[node].size()) {
leaf[node] = 1;
}
}
int main() {
int N = 8;
vector<int> tree[N + 1];
insertNode(1, 2, tree);
insertNode(1, 3, tree);
insertNode(3, 4, tree);
insertNode(3, 5, tree);
insertNode(3, 6, tree);
insertNode(4, 7, tree);
insertNode(4, 8, tree);
int leaf[N + 1];
int visited[N + 1];
for (int i = 0; i <= N; i++) {
visited[i] = 0;
}
DFS(1, leaf, visited, tree);
for (int i = 1; i <= N; i++) {
cout << i << "->" << leaf[i] << endl;
}
return 0;
}코드 동작 원리
DFS 함수는 각 노드를 방문할 때마다 해당 노드의 리프 개수를 0으로 초기화하고, 자식 노드들을 재귀적으로 순회합니다. 자식 노드의 탐색이 완료되면 그 자식의 리프 개수를 현재 노드에 누적합니다. 만약 어떤 노드가 자식이 없다면 그 노드 자체가 리프 노드이므로 값을 1로 설정합니다. 이렇게 하면 재귀 호출이 모두 끝났을 때 각 노드의 하위 트리에 포함된 리프 노드의 총 개수를 얻을 수 있습니다.
실행 결과
위 코드를 컴파일하여 실행하면 다음과 같은 결과를 얻을 수 있습니다.
1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1
시간 복잡도 분석
이 알고리즘은 DFS를 통해 트리의 각 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(N)입니다. 여기서 N은 트리에 있는 노드의 총 개수입니다. 공간 복잡도 역시 리프 개수 배열, 방문 여부 배열, 그리고 재귀 호출 스택 때문에 O(N)이 됩니다. 따라서 이 접근 방식은 대규모 트리에서도 효율적으로 동작합니다.