이 글에서는 C++을 활용해 하나의 트리를 짝수 개의 노드로 이루어진 포리스트(forest)로 변환하는 알고리즘을 소개합니다.
N개의 노드로 구성된 트리가 주어졌을 때, 분리된 각각의 트리가 모두 짝수 개의 노드를 갖도록 만들기 위해 제거할 수 있는 간선의 최대 개수를 구하는 것이 목표입니다.
접근 방식: 깊이 우선 탐색(DFS)
이 문제는 DFS 한 번의 순회만으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 루트 노드에서 DFS를 시작해 각 서브트리에 포함된 노드의 개수를 계산합니다.
- 어떤 서브트리의 노드 수가 짝수라면, 해당 서브트리를 부모로부터 분리해도 나머지 트리의 구조에는 영향을 주지 않습니다.
- 따라서 노드 수가 짝수인 서브트리를 발견할 때마다 제거 가능한 간선 수를 1씩 늘립니다.
모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(N)이며, 방문 배열과 재귀 호출 스택을 고려한 공간 복잡도 역시 O(N)입니다.
C++ 구현 예제
#include<bits/stdc++.h>
#define N 12
using namespace std;
//루트 노드를 포함하는 서브트리의 노드 수를 반환하는 함수
int depth_search(vector<int> tree[N], int visit[N], int *ans, int node){
int num = 0, temp = 0;
//현재 노드를 방문 처리
visit[node] = 1;
for (int i = 0; i < tree[node].size(); i++){
if (visit[tree[node][i]] == 0){
//하위 서브트리의 총 노드 수 계산
temp = depth_search(tree, visit, ans, tree[node][i]);
//노드 수가 짝수면 제거 간선 수 1 증가, 홀수면 현재 값에 누적
(temp%2)?(num += temp):((*ans)++);
}
}
return num+1;
}
//제거할 수 있는 최대 간선 수를 반환하는 함수
int print_maxedge(vector<int> tree[N], int n){
int visit[n+2];
int ans = 0;
memset(visit, 0, sizeof visit);
depth_search(tree, visit, &ans, 1);
return ans;
}
int main(){
int n = 10;
vector<int> tree[n+2];
tree[1].push_back(3);
tree[3].push_back(1);
tree[1].push_back(6);
tree[6].push_back(1);
tree[1].push_back(2);
tree[2].push_back(1);
tree[3].push_back(4);
tree[4].push_back(3);
tree[6].push_back(8);
tree[8].push_back(6);
tree[2].push_back(7);
tree[7].push_back(2);
tree[2].push_back(5);
tree[5].push_back(2);
tree[4].push_back(9);
tree[9].push_back(4);
tree[4].push_back(10);
tree[10].push_back(4);
cout << print_maxedge(tree, n) << endl;
return 0;
}실행 결과
2
동작 과정 상세 설명
예제 트리는 총 10개의 노드로 구성되어 있으며, 루트(노드 1)를 기준으로 각 서브트리의 크기는 다음과 같습니다.
- 노드 3을 루트로 하는 서브트리: 4개(3, 4, 9, 10) → 짝수이므로 간선 (1, 3) 제거 가능
- 노드 6을 루트로 하는 서브트리: 2개(6, 8) → 짝수이므로 간선 (1, 6) 제거 가능
- 노드 2를 루트로 하는 서브트리: 3개(2, 7, 5) → 홀수이므로 제거 불가
결국 간선 두 개를 제거하면 {3, 4, 9, 10}, {6, 8}, {1, 2, 7, 5} 세 개의 트리로 이루어진 포리스트가 되며, 모든 트리가 짝수 개의 노드를 가지게 됩니다. 따라서 정답은 2입니다.