문제 설명
정점(노드)의 개수가 짝수인 무방향 트리가 주어졌을 때, 결과로 만들어지는 숲(forest)의 모든 연결 요소(컴포넌트)가 짝수 개의 정점을 갖도록 트리에서 제거할 수 있는 최대 간선(edge)의 개수를 구하는 것이 이 문제의 목표입니다.
예시
위 그림의 트리에서는 빨간색으로 표시된 간선 0-2와 0-4, 총 2개의 간선을 제거하면, 남은 모든 연결 요소가 짝수 개의 정점으로 구성됩니다.
알고리즘 접근 방식
핵심 아이디어는 DFS(깊이 우선 탐색)를 활용해 각 서브트리의 정점 개수를 세는 것입니다. 어떤 서브트리의 정점 수가 짝수라면, 해당 서브트리를 부모와 분리하는 간선을 안전하게 잘라낼 수 있습니다.
- 트리는 연결되어 있으므로 임의의 노드에서 DFS를 시작합니다.
- 현재 노드를 루트로 하는 서브트리의 노드 개수를 저장할 카운터를 0으로 초기화합니다.
- 현재 노드의 모든 자식 서브트리에 대해 재귀적으로 다음을 수행합니다.
- 현재 서브트리의 크기가 짝수라면 → 해당 서브트리를 분리할 수 있으므로 결과값(result)을 1 증가시킵니다.
- 크기가 홀수라면 → 현재 카운트에 해당 서브트리의 노드 수를 더합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int dfs(vector<int> g[], int u, bool visit[], int& res) {
visit[u] = true;
int currComponentNode = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (!visit[v]) {
int subtreeNodeCount = dfs(g, v, visit, res);
if (subtreeNodeCount % 2 == 0)
res++;
else
currComponentNode += subtreeNodeCount;
}
}
return (currComponentNode + 1);
}
int maxEdgeRemovalToMakeForestEven(vector<int> g[], int N) {
bool visit[N + 1];
for (int i = 0; i <= N; i++)
visit[i] = false;
int res = 0;
dfs(g, 0, visit, res);
return res;
}
void addEdge(vector<int> g[], int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
int main() {
int edges[][2] = {{0, 2}, {0, 1}, {0, 4}, {2, 3}, {4, 5}, {5, 6}, {5, 7}};
int N = sizeof(edges)/sizeof(edges[0]);
vector<int> g[N + 1];
for (int i = 0; i < N; i++)
addEdge(g, edges[i][0], edges[i][1]);
cout << "Answer = " << maxEdgeRemovalToMakeForestEven(g, N) << endl;
return 0;
}출력 결과
Answer = 2
동작 원리 및 복잡도
DFS는 트리의 모든 노드를 정확히 한 번씩 방문하며, 각 노드에서 자신의 서브트리 크기를 계산합니다. 서브트리 크기가 짝수일 때마다 간선 하나를 제거할 수 있으므로, 전체 시간 복잡도는 O(N)입니다. 여기서 N은 트리의 정점 개수입니다. 공간 복잡도 역시 방문 배열과 인접 리스트 저장에 사용되는 O(N)입니다.