[BOJ 19274] Antennas On Tree

https://www.acmicpc.net/problem/19274

 

앳코더를 사랑하는 나에게는 정말 익숙한 이름인 Snuke좌가 나오는 문제다. 대학생을 대상으로 하는 러시아 캠프(페트로 뭐시기)에서 앳코더쪽 사람들이 낸 문제인 것 같았다. 그래서 그런지 문제 스타일도 앳코더 스타일 느낌이 강하다. 코딩 간단, 디스크립션 간단, 아이디어성.

 

문제

정점이 $N$개인 트리가 주어진다. 우리는 적당히 $K$개의 정점 $x_1, x_2, \cdots, x_K$를 선택하여 임의의 정점 $i$에 대해 $(d(x_1, i), d(x_2, i), \cdots, d(x_K, i))$가 모두 다르도록 할 것이다. 다시 말해, $K$개의 정점을 골라 각 정점들로부터의 거리 정보 벡터로부터 어떤 점인지 알아낼 수 있도록 $K$개의 정점을 골라야 한다는 것이다. 이 때 가장 작은 $K$는?

 

풀이

만약 모든 정점의 차수가 2 이하라고 해보자. 이러한 경우, 트리가 일직선 형태이기 때문에 답이 1임은 자명하다.

 

정점의 차수가 3 이상인 어떤 정점을 루트로 두고 문제를 풀어보자. 생각해보면 당연하게 루트의 서브트리들 중 적어도 2개의 서브트리에는 고른 정점이 존재해야 한다. 정확히는 (루트의 자식 수 - 1)개의 서브트리에 고른 정점이 존재해야 한다. 그렇지 않은 경우 어떤 일을 해도 고른 정점이 없는 두 개 이상의 서브트리에서 깊이가 같은 두 정점을 구분할 수 없다. 때문에 우리는 모든 서브트리에 대하여, 해당 서브트리의 외부에 적어도 고른 정점이 하나 존재한다는 가정을 할 수 있다. (이것이 정점 차수가 3 이상인 정점을 루트로 잡은 이유다.)

 

이제 $dp_i$를 정의하자. $dp_i$는 $i$번 정점을 루트로 하는 서브트리의 외부에 적어도 한 개의 정점을 고른 상태에서 $i$번 정점을 루트로 하는 서브트리 내부의 정점을 모두 구별 가능하도록 골라야 하는 최소 정점 수이다.

이렇게 정의할 경우, $dp_i$는 엄밀하지 않게 생각하면, 그냥 자식의 $dp$값을 모두 더하면 된다.

여기서 $dp$값이 $0$인 것과 $0$이 아닌 것의 구분이 필요하다. $dp$값이 $0$인 경우는 일직선인 형태밖에 없다. 만약 $dp$값이 $0$보다 크다면 다른 서브트리와 합쳐 생각해도 해당 서브트리에는 별도로 정점을 추가할 필요가 없다. 해당 서브트리에서 고른 정점들과 외부에서 고른 하나의 정점으로 해당 서브트리 내부의 모든 정점이 구분 가능하기 때문이다. 하지만 $dp$값이 $0$인 자식들이 $k$개 있다고 한다면, 즉 일직선인 형태가 $k$개 붙어있다고 생각하면, 이 중에서 $k-1$개에 정점을 하나씩 추가로 할애해야 어느 직선의 정점인지 구분할 수 있다. 따라서 $dp_i$를 구할 때 자식의 $dp$값을 모두 더하고, (자식 중 $dp$값이 $0$인 것의 개수 - 1)을 더하면 된다. ($dp$값이 0인 것의 개수가 2개 이상일 때)

리프 노드일 때는 자명하게 $dp$값이 0이므로, dfs 등 어떤 방법으로든 $dp$값을 채워준 뒤 루트 정점의 $dp$값을 출력하면 된다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define reset(x) memset(x, 0, sizeof(x))

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

vector <int> g[MAX];
int dp[MAX], L[MAX];

void dfs(int x, int pa) {
    if(g[x].size() == 1) return;
    int cnt = 0;
    for(auto i : g[x]) {
        if(i == pa) continue;
        dfs(i, x);
        dp[x] += dp[i];
        if(dp[i] == 0) cnt++;
    }
    dp[x] += max(0, cnt - 1);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n;
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u++, v++;
        g[u].eb(v), g[v].eb(u);
    }

    for(int i = 1; i <= n; i++) {
        if(g[i].size() > 2) {
            dfs(i, 0);
            cout << dp[i];

            return 0;
        }
    }
    cout << 1;
}