[백준 2533] 사회망 서비스(SNS) C++

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

트리에서의 다이나믹 프로그래밍 입문 #3

 

[백준 1949] 우수 마을 C++

지난 포스팅 우수마을과 다르게

dp[now][0] -> 현재 친구가 얼리어답터가 아니라면 연결된 모든 친구는 얼리어답터여야 한다

이므로 dp[now][0] += dp[next][1]; 와 같이 쓸 수 있다

 

그리고 얼리어답터인 친구끼리 붙을 수 있기 때문에 아래와 같은 식을 통해 연결된 친구가 얼리어답터인지 아닌지 라는 2개의 경우에 따라 최솟값을 갱신한다

dp[now][1] += min(dp[next][0], dp[next][1]);

#include <iostream>
#include <vector>
 
using namespace std;
 
int N;
vector<int> tree[1000001];
 
// now가 루트일 때의 서브트리에서 얼리아답터의 최소 수
int dp[1000001][2];
bool visited[1000001];
 
void input(){
    int u, v;
    cin >> N;
    for(int i = 0; i < N-1; i++){
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
}
 
void dfs(int now){
    visited[now] = true;
    
    dp[now][0] = 0;
    dp[now][1] = 1;
    
    for(int i = 0; i < tree[now].size(); i++){
        int next = tree[now][i];
        if(visited[next]) continue;
        dfs(next);
        
        dp[now][0] += dp[next][1];
        dp[now][1] += min(dp[next][0], dp[next][1]);
    }
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    dfs(1);
    cout << min(dp[1][0], dp[1][1]);
    return 0;
}

dfs, 양방향 트리, 2차원 DP배열

 

미래의 나는 트리에서의 다이나믹 프로그래밍을 잊을 것이다

이걸 보고 다시 떠올려 주면 좋겠다