[백준] 2533: 사회망 서비스

0. 문제 주소

 

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

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

 

 

1. 풀이

 

대표적인 tree DP 문제.

 

먼저 연결 관계로 vector<int> 배열 child를 이용해 트리를 만들고,

dp[i][j] = (i번째 node가 j번째 상태일 때, 이를 root로 갖는 subtree에서의 얼리어답터 최소 명수)로 저장한다.

상태는 1일 때 이 node가 얼리어답터, 0일 때 아니라는 것이다.

 

 

얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 

 

라는 조건이 중요하다.

 

트리의 관점에서, 자신의 부모가 얼리어답터냐 / 아니냐 의 경우를 보자.

 

 

---

-- 부모가 얼리어답터일 때

 

자녀는 얼리어답터여도 되고, 아니어도 된다.

 

 

-- 부모가 얼리어답터가 아닐 때

 

자녀는 반드시 얼리어답터여야 한다.

---

 

 

이를 이용해서 top-down 방식으로 root node부터 아래로 쭉 순회하며, dp 테이블을 갱신한다.

 

root node가 얼리어답터일 때, 아닐 때 두가지 경우 중 최소 값을 답을 출력하면 된다.

 

 

 

2. 풀이 코드

 

* 유의할 점

 

1. root 함수에서, (ret != -1)일 때 ret을 return하게 해주는 구문을 써주어야 중복 계산을 피할 수 있다.

 

#include <bits/stdc++.h>
#define MAX 1000005

using namespace std;

int N;
vector<int> adj[MAX];
vector<int> child[MAX];
bool visited[MAX];
int dp[MAX][2];

void make_tree(int curr){
    visited[curr] = true;

    for (int next: adj[curr]){
        if (!visited[next]){
            child[curr].push_back(next);
            make_tree(next);
        }
    }
}

int root(int curr, int stat){
    printf("%d %d\n", curr, stat);
    int& ret = dp[curr][stat];
    if (ret != -1) return ret;
    // 이걸 안 써주면 여러 번 나올 수 있는 dp[2][1] 등과 같은 값을 계속 계산해 주어야 함

    ret = 0;

    if (!stat) {
        for (int next: child[curr]){
            ret += root(next, 1);
        }
    }
    else{
        for (int next: child[curr]){
            ret += min(root(next, 0), root(next, 1));
        }
        ret++; // stat == 1 -> curr가 얼리어답터임
    }
    return ret;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &N);
    for (int i=0;i<N;i++){
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    make_tree(1);

    memset(dp, -1, sizeof(dp));
    printf("%d\n", min(root(1, 0), root(1, 1)));

}