이 문제에서는 n-ary 트리를 나타내는 인접 리스트(adjacency list)가 주어지며, 우리의 목표는 이 트리에서 크기가 짝수인 하위 트리(even size subtree)의 개수를 찾는 것입니다.
n-ary 트리란?
n-ary 트리는 노드들의 집합으로, 일반적으로 다음과 같은 계층적 구조로 표현됩니다.
- 트리는 루트(root) 노드에서 시작합니다.
- 트리의 각 노드는 자신의 자식 노드들을 가리키는 포인터 목록을 가집니다.
- 자식 노드의 개수는 m개 이하입니다.
문제 이해를 위한 예시
입력:
출력: 4
설명:
- 루트가 7인 서브트리의 크기는 8로 짝수입니다.
- 루트가 2인 서브트리의 크기는 4로 짝수입니다.
- 루트가 0인 서브트리의 크기는 2로 짝수입니다.
- 루트가 3인 서브트리의 크기는 2로 짝수입니다.
해결 접근 방법
가장 직관적인 방법은 특정 노드를 루트로 하는 서브트리에 속한 모든 노드의 개수를 합산하고, 그 값이 짝수라면 evenTreeCount를 1 증가시키는 것입니다. 이를 위해 DFS(깊이 우선 탐색)를 활용하여 각 노드의 서브트리 크기를 구할 수 있습니다.
핵심 아이디어는 트리를 단 한 번의 순회로 처리하는 것입니다. 재귀적으로 각 자식 노드의 서브트리 크기를 구한 뒤, 자기 자신을 포함한 전체 서브트리의 크기를 계산하고, 그 값이 짝수이면 카운트를 증가시킵니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
// v를 루트로 하는 서브트리의 크기를 반환하며,
// 크기가 짝수이면 EvenCount를 증가시킵니다.
int countEventSizeSubTree(vector<int> adj[], int n, int v, int& EvenCount){
int size = 1; // 자기 자신 포함
for (auto ele : adj[v]) {
size += countEventSizeSubTree(adj, n, ele, EvenCount);
}
if (size % 2 == 0)
EvenCount++;
return size;
}
int main(){
int n;
n = 10; // 노드 번호의 최댓값
vector<int> adj[n + 1];
// 인접 리스트로 트리 구성
adj[7].push_back(2);
adj[7].push_back(9);
adj[2].push_back(0);
adj[2].push_back(1);
adj[9].push_back(3);
adj[3].push_back(8);
adj[0].push_back(5);
int EvenCount = 0;
// 루트 노드 7부터 탐색 시작
countEventSizeSubTree(adj, n, 7, EvenCount);
cout<<"Even Size SubTree are "<<EvenCount;
return 0;
}
실행 결과
Even Size SubTree are 4
코드 설명
countEventSizeSubTree 함수는 현재 노드 v의 크기를 1로 초기화한 후, 인접 리스트를 순회하며 각 자식 노드에 대해 재귀적으로 함수를 호출합니다. 모든 자식의 서브트리 크기가 더해지면 현재 서브트리의 전체 크기가 완성되고, 이 값이 2로 나누어떨어지면 EvenCount를 증가시킨 뒤 크기를 상위 호출자에게 반환합니다. 메인 함수에서는 루트 노드 7부터 탐색을 시작하여 전체 트리에서 짝수 크기 서브트리의 총 개수를 출력합니다.
복잡도 분석
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 재귀 호출 스택의 깊이는 트리의 높이에 비례하므로, 공간 복잡도는 균형 잡힌 트리의 경우 O(log n), 편향된 트리의 경우 최악 O(n)입니다.