이 튜토리얼에서는 n-ary 트리의 모든 노드에 대한 리프 노드의 수를 찾는 프로그램을 작성할 것입니다.
n-ary 트리가 주어지면 모든 하위 트리에 대한 리프 노드 수를 찾아야 합니다. 예를 들어 보겠습니다.
입력
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
알고리즘
-
원하는 트리로 n-ary 트리를 초기화합니다.
-
DFS를 사용하여 트리를 탐색합니다.
-
각 노드 리프 노드 수를 저장할 배열을 유지합니다.
-
DFS에 대한 재귀 호출 후 리프 노드 수를 늘립니다.
-
리프 노드 수로 모든 노드를 인쇄합니다.
구현
다음은 위의 알고리즘을 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;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1