[BOJ] 2533 - 사회망 서비스 (C++)

문제

사회망 서비스

코드

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> e[1000001];
bool visited[1000001];
int dp[1000001][2]; // 0: early, 1: not

void find(int x){
    visited[x] = true;

    dp[x][0] = 1;
    for (int i = 0; i < e[x].size(); i++){
        int child = e[x][i];
        if (visited[child]) continue;
        find(child);
        dp[x][1] += dp[child][0];
        dp[x][0] += min(dp[child][1], dp[child][0]);
    }
}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N;
    int u, v;
    for (int i = 0; i < N-1;i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    find(1);
    cout << min(dp[1][0], dp[1][1]);
    return 0;
}

접근

노드마다 유지하는 상태를 0과 1로 구분하였다.

dp[node][0] : 해당 노드가 얼리 어답터일 경우 조건을 만족하는 최소 얼리 어답터의 수
dp[node][1] : 해당 노드가 일반인일 경우 조건을 만족하는 최소 얼리 어답터의 수

만약 현재 노드가 일반인인 경우 모든 자식 노드들이 얼리 어답터야 하므로 자식들의 값을 더해주면 된다. 하지만 현재 노드가 얼리 어답터인 경우 자식노드가 일반인(얼리 어답터)일 때가 최적해라는 것을 보장하진 못한다. 따라서 이때는 둘 중 더 작은 값을 유지해야 한다.

dp[x][1] += dp[child][0]; // 일반인
dp[x][0] += min(dp[child][1],dp[child][0]); // 얼리 어답터

이때 탐색을 시작하는 루트 노드는 임의로 결정해도 무방하다. 결국 재귀 함수를 통해 leaf node까지 탐색하게 되기 때문이다.