백준 2533 사회망 서비스 - 가장 쉽고 자세한 트리 dp로 푸는 방법

문제 링크

www.acmicpc.net/problem/2533

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

풀이 아이디어

이 문제는 각 노드별로 단 2가지 state밖에 없다. 

해당 노드가 얼리 어답터이거나, 그냥 일반인이거나.

두 state는 완전히 독립적이므로, 다이나믹 프로그래밍의 적용이 가능하다.

 

dp[node][0] : 해당 노드가 얼리 어답터일 경우, 본인 노드 + 해당 노드의 모든 자식노드 중 문제 조건을 만족하는 최소얼리어답터 수

dp[node][1] : 해당 노드가 일반인일 경우, (이하 동문)

 

로 문제를 쪼개 나가면서 풀 수 있다.

find(아무 노드나 상관없음)으로 다이나믹 프로그래밍을 돌린 뒤

마지막에는 dp[(아무 노드나 상관없음)][0],[1] 중 작은 값 이 정답이 된다.

아무 노드나 상관없는 이유는 어차피 traversing을 통해 끝까지 탐색이 진행되기 때문이다.

다만 find와 dp 위 두줄의 '아무 노드'는 같은 노드여야 한다.

 

여기까지가 트리dp의 전형적인 진행 방식이다.

편의상 1을 루트노드라고 가정하고 그림으로 표시해 보면 다음과 같다.

부모노드가 일반인일 경우, 자식 노드는 전부 얼리어답터 여야 하므로 해당하는 dp 값을 전부 더해줘야 하지만,

부모노드가 얼리어답터일 경우 자식노드가 얼리어답터가 아닌 경우가 최적해라는 보장이 없다.

부모노드가 따라서 얼리어답터일 경우는 자식 노드가 얼리 어답터일 경우와 아닐 경우 중 더 작은 값을 골라 dp값으로 넣어줘야 한다.

식으로 표현하면 다음과 같다.

dp[x][1]+=dp[child][0];
dp[x][0]+=min(dp[child][1],dp[child][0]);

 

코드

#include <bits/stdc++.h>
using namespace std;

int n,parent;
vector<int> e[1000001];
int dp[1000001][2]; //0이 어답터, 1이 일반인
bool visited[1000001];

void find(int x){
    visited[x]=true;
    dp[x][0]=1;
    for(int i=0; i<e[x].size(); i++){
        int child = e[x][i];
        if(visited[child]) continue;
        find(child);
        dp[x][1]+=dp[child][0];
        dp[x][0]+=min(dp[child][1],dp[child][0]);
    }

}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    int u,v;
    for(int i=0; i<n-1; i++){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    find(1);
    cout<<min(dp[1][0],dp[1][1]);
}