Back to : algorithms
  • 난이도 : Gold 3
  • solved ac class 6 essential

풀이

트리에서 최소한의 노드를 골라서, 모든 간선을 커버하도록 하는, minimum vertex cover 문제이다. 일반적인 그래프에서는 NP-Hard이지만, 트리에는 쉽게 해결할 수 있다.

임의로 루트를 잡았을 때, 리프 노드는 반드시 마킹하지 않는 것이 유리함을 알 수 있다. 리프 노드는 바로 그 위 부모 노드만 마킹되면 되고, 그 노드가 여러 개의 리프를 가질 수도 있으므로, 리프 노드는 항상 마킹하지 않는 것이 유리하다. 따라서, 리프 노드의 부모가 되는 노드는 반드시 마킹해야 한다.

이를 반복해서, 마킹할 필요가 있는 노드를 트리의 아래쪽에서부터 찾으면 되고, 이는 DFS를 역순으로 돌면서 마킹하는 셈이 된다. 위 규칙을 적용해 본 후, 자식노드중 마킹되지 않은 노드가 있으면 지금 보는 노드를 마킹하고, 그렇지 않으면 나를 마킹하지 않음으로써 부모노드를 마킹해야 함을 기억하면 된다.

Code

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

vector <int> T[1010101];
int ea[1010101], e;

bool dfs(int r, int p)
{
    if (T[r].size() == 1 && T[r][0] == p)
        return false;
    bool cea = true;
    for (auto it:T[r])
        if (it != p)
            cea &= dfs(it, r);
    return ea[r] = !cea;
}

int32_t main()
{
    usecppio
    int n; cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v; cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        if (ea[i])
            e++;
    cout << e << '\n';
}