[boj] 백준 2533 사회망 서비스 (c++) - 트리, dp

[문제]

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

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

 

[풀이]

트리 형태에서 dp를 이용해 푸는 문제. dp로 풀어야 한다고는 생각도 못했다.

생각해보면 이 문제에서는 딱 2가지만 고려하면 된다.

1. 부모 노드가 얼리어답터가 아니라면, 자식 노드는 무조건 얼리어답터여야 한다. (부모 노드를 얼리어답터로 만들기 위해서)

2. 부모 노드가 얼리어답터라면, 자식 노드는 얼리어답터여도 되고, 얼리어답터가 아니어도 된다. (자식 노드가 얼리어답터가 아니어도,  1번 조건을 충족하기 위해 자식의 자식 노드는 무조건 얼리어답터여야 한다. 그렇게 되면 자식 노드도 얼리어답터가 될 수 있다. 만약 자식 노드가 리프 노드면 부모 노드가 얼리어답터이므로 당연히 얼리어답터가 될 수 있다.)

 

 따라서 부모에서 자식으로 연결된 단방향 트리를 부모 노드부터 dfs를 돌리면서 dp 배열에 저장해주면 된다. 

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define INF 987654321

using namespace std;

int n;
vector<int> adj[1000001];
vector<int> tree[1000001];
bool visited[1000001];
int dp[1000001][2]; //얼리어답터일 때, 아닐 때

void dfs(int node){
    dp[node][0] = 0; // 본인이 얼리가 아니면 얼리 개수 0
    dp[node][1] = 1; // 본인이 얼리면 얼리 개수 1

    for(int i=0; i<tree[node].size(); i++){
        int child = tree[node][i];

        dfs(child);

        dp[node][0] += dp[child][1]; //부모가 얼리어답터가 아니면 자식은 무조건 얼리어답터여야 한다.
        dp[node][1] += min(dp[child][0], dp[child][1]); //부모가 얼리어답터면 자식은 얼리어답터여도, 아니어도 된다.
    }
}

void make_tree(int node){
    visited[node] = true;
    for(int i=0; i<adj[node].size(); i++){
        int next = adj[node][i];
        if(visited[next]) continue; //단방향
        tree[node].push_back(next);
        make_tree(next);
    }
}

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

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

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

}