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

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

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

인접한 정점들의 관계에 따라 tree dp를 이용하여 푸는 문제이다.

 

만약 현재 정점을 선택하지 않는다면, 다음 정점은 선택해야한다.

만약 현재 정점을 선택하면, 다음 정점은 선택해도 안해도 된다.

 

이를 이용하여 dp테이블을 채워가며 답을 구한다.

dp테이블을 다음과 같이 정의하자.

dp[ i ][ j ] : i번째 정점을 선택할 때 j = 1, 선택하지 않을 때 j = 0이고, 그 때의 최솟값을 기록한다.

그러면 현재 정점을 cur, 다음 정점을 next라 할 때, 이렇게 dp테이블을 채울 수 있다.

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

정답 코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> tree[1000100];
int dp[1000100][2];
int visited[1000100];
void dfs(int cur){
    if(visited[cur])
        return;
    visited[cur] = 1;
    dp[cur][0] = 0;
    dp[cur][1] = 1;
    for(auto next : tree[cur]){
        if(visited[next])
            continue;
        dfs(next);
        dp[cur][0] += dp[next][1];
        dp[cur][1] += min(dp[next][1],dp[next][0]);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1; i<n; i++){
        int u,v; cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1);
    cout << min(dp[1][0],dp[1][1]);
    return 0;
}