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

문제

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

 

코드

/*
    본인이 얼리어답터라면 자식노드는 얼리어답터 이거나 아니어도 된다.
    본인이 얼리어답터가 아니라면 자식 노드는 반드시 얼리어답터여야 한다.
*/

#include <iostream>
#include <vector>
using namespace std;

vector<int>graph[1000001];
int dp[1000001][2]; //본인이 얼리답터일떄, 본인이 얼리어답터가 아닐때
int N;

void dfs(int node, int before){
    dp[node][0] = 0;
    dp[node][1] = 1;
    for(auto next: graph[node]){
        if(next != before){
            dfs(next,node);
            dp[node][0] += dp[next][1];
            dp[node][1] += min(dp[next][0], dp[next][1]);
        }
    }
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    for(int i=0; i<N-1; i++){
        int a, b; cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=0; i<100001; i++){
        dp[i][0] = 1e9;
        dp[i][1] = 1e9;
    }
    
    dfs(1, 0);
    cout<< min(dp[1][0], dp[1][1]);
}

 

풀이

트리에서의 dp 문제였습니다.

dp[node][2] 의 배열을 생성합니다. 배열은 아래를 의미합니다.

• dp[node][0]: 해당 노드가 얼리어답터가 아닐 때 본인 자식의 얼리어답터 수
• dp[node][1]: 해당 노드가 얼리어답터일 때 본인 자식의 얼리어답터 수

dfs 도입부에 아래와 같이 배열을 세팅합니다.

• dp[node][0] = 0;  본인이 얼리어답터가 아니기에 얼리어답터 수를 증가하지 않습니다. 
• dp[node][1] = 1;  본인이 얼리어답터이기에 얼리어답터 수를 증가시킵니다.

그 후 dfs를 탐색한 후 아래와 같이 세팅합니다.

• dp[node][0] += dp[next][1];  본인이 얼리어답터가 아니라면 자식 노드는 반드시 얼리어답터여야 하기 때문입니다.
• dp[node][1] += min(dp[next][0], dp[next][1]);  본인이 얼리어답터라면 자식 노드는 얼리어답터이거나 아니거나 둘 다 가능하기 때문에 작은 값으로 갱신해줍니다.

그 후 루트 노드인 1번이 얼리어답터일 때와 아닐 때의 최솟값을 출력하면 됩니다.