BOJ 2533 사회망 서비스(SNS)

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

2533번: 사회망 서비스(SNS)

 

트리 DP 문제입니다. 트리의 어떤 노드 $N$에 대해,

 

$dp[N][0] = N$을 루트로 하는 트리에서, $N$이 얼리어답터가 아닐 때 이 트리의 모든 사람에게 아이디어가 전파되기 위한 최소 얼리어답터의 수.

 

$dp[N][1] = N$을 루트로 하는 트리에서, $N$이 얼리어답터 일 때 이 트리의 모든 사람에게 아이디어가 전파되기 위한 최소 얼리어답터의 수.

 

라고 정의합시다. 그러면 답은 $min(dp[1][0], dp[1][1])$ 입니다(전체 트리의 루트 노드는 어떤 노드라도 상관 없지만, 편의상 그냥 1번 노드라고 합시다). 또한 이러한 dp 식은 트리의 부모와 자식간의 관계를 통해 재귀적으로 정의할 수 있습니다. 우리가 지금 dp 값을 구하고자 하는 노드의 인덱스를 i라고 할 때,

 

$dp[i][0] = dp[c1][1] + dp[c2][1] + ...$ 입니다. 즉, 노드 $i$가 얼리어답터가 아니라면, 그의 모든 자식들이 얼리어답터여야 합니다.

 

$dp[i][1] = 1 + min(dp[c1][0], dp[c1][1]) + min(dp[c2][0], dp[c2][1]) + ...$ 입니다. 노드 $i$가 얼리어답터라면, 그의 자식들은 얼리어답터이든 아니든 상관 없습니다. 그러므로 모든 자식들에 대해 둘 중 더 작은 값을 택해서 더해줍니다. 앞에 $+1$이 붙은 이유는, 노드 $i$가 얼리어답터이므로 $1$을 더해준 것입니다.

 

즉, 자식의 dp값이 구해졌다면 부모의 dp값을 구할 수 있습니다. 그러므로 트리에서 dfs를 통해 dp값을 쭉 올려주면 됩니다.

 

 

#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
int dp[1000001][2];
vector<int> adj[1000001];

void go(int n, bool early, int p) {
    if (dp[n][early] != 0) return;
    // 내가 얼리어답터일때
    if (early) {
        dp[n][1] = 1;
        for (int a : adj[n]) {
            if (a == p) continue;
            go(a, false, n);
            go(a, true, n);
            dp[n][1] += min(dp[a][1], dp[a][0]);
        }
    }
    // 얼리어답터 아닐때
    else {
        for (int a : adj[n]) {
            if (a == p) continue;
            go(a, true, n);
            dp[n][0] += dp[a][1];
        }
    }
}


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


    int N;
    cin >> N;

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    go(1, true, 0);
    go(1, false, 0);

    cout << min(dp[1][0], dp[1][1]);
      
}