백준 2533번: 사회망 서비스(SNS) (C++)

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

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

---

Solved By: DP in Tree

 

(공부한 풀이 출처: https://hqjang.tistory.com/104)

우선 이분법적으로 생각할 수 있습니다. 어떤 노드는 2가지 상태밖에 지니지 못 합니다.

1. 일반인인 경우

2. 얼리어답터인 경우

 

두 가지 경우에 대해서 생각해봅시다.

 

[일반인인 경우]

어떤 노드가 일반인이라면 자식 노드들은 전부 얼리어답터여야 합니다.

[얼리어답터인 경우]

어떤 노드가 얼리어답터이라면 자식 노드는 두 가지 state 중 어떤 state여도 상관이 없습니다.

하지만, 문제의 요구에 따라 자식 노드가 어떤 state를 가지는 것이 최솟값을 유발하는가가 중요합니다.

 

즉, 문제를 풀 수 있는 방법은 한 노드에게 두 가지 state의 대한 값을 가지게 하는 것입니다.

노드가 [얼리어답터인 경우], [일반인인 경우]로 나누어 DFS를 통해 Traversal을 하여 값을 구할 수 있습니다.

 

이 과정에서 State들이 독립적이지만 서로의 값을 가지는데에는 영향을 끼치기 때문에 DP를 통해 풀 수 있습니다. 

#include <iostream>
#include <vector>
#define MAX 1000001
using namespace std;

int n;
vector<int> adj[MAX];
bool visited[MAX];
int cache[MAX][2];

void find(int cur){
    visited[cur] = true;
    cache[cur][0] = 1;
    for(auto nxt : adj[cur]){
        if(visited[nxt]) continue;
        find(nxt);
        cache[cur][1] += cache[nxt][0];
        cache[cur][0] += min(cache[nxt][0], cache[nxt][1]);
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    find(1);
    cout << min(cache[1][1], cache[1][0]);
    return 0;
}