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

www.acmicpc.net/problem/2533

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

 

백준 사회망 서비스 문제는 트리에서 경우의 수를 구하는 다이나믹 프로그래밍 문제입니다.

 

서로 연결된 친구들 중에서 얼리아답터가 아닌 노드는 하나 이상의 얼리아답터와 연결되어있어야합니다. 그 때 최소 얼리 아답타를 구하는 문제입니다.

 

노드 1부터 시작해서 연결되어 있는 모든 노드를 DFS로 찾아가면서 경우수를 만들어주고, Return 하면서 경우의 수를 1만큼 증가 시켜준다음 누적합을 return해주시면 되겠습니다. 

 

이 문제를 처음에는 친구끼리 연결은 단방향으로 연결시켜주었는데, 정답이 맞지 않았습니다.

입력값으로 들어올 때, 양방향으로 친구들 사이에 간선을 만들어주고, DFS로 탐색하면서 부모를 거꾸로 찾아가는 경우의수는 continu할 수 있도록 패스시킵니다. 

 

따라서, 양방향 간선을 만들어 준뒤, 다시 Tree를 만들어야했습니다.

 

만든 Tree구조에서 isAdaptor를 0, 1로 구분짓게 하여, 0일 때는 얼리 아답터가 아닐 때, 1은 얼리 아답터일 때로 정의했습니다.

 

따라서, DFS 탐색하면서 DP 배열에 -> DP[node][isAdaptor]이 초기값 -1이 아닌 값이 들어 있다면, 이미 이 노드로부터 경우의 수를 다 계산했으니 해당 값을 return을 해줍니다.

 

그래서 isAdaptor = 1일 때, 해당 노드가 얼리아답터라는 의미이기 때문에 dp 해당 배열을 1로 만들어줍니다(자식 노드들을 모두 탐색 후 누적합을 구하기 위해서입니다. 1은 자기 자신이 경우의 수가 1가지가 된다는 의미)

 

isAdaptor 가 1일 땐 연결된 노드들이 isAdaptor가 1이 되어되 괜찮고, 0이 되어도 괜찮습니다. 2가지의 경우를 DFS탐색을 다시 실행합니다.

해당 노드들을 탐색 후 반환 된 값은 isAdaptor가 0일 때, isAdaptor가 1일 때 두 가지 경우를 탐색하고 나서 반환 된 값입니다. 

문제에서 요구하는 것은 얼리아답터가 최소가 되는 것이기 때문에 반환된 값 중에 최솟값을 취해주셔서 누적합을 구하면 됩니다.

 

 

isAdaptor가 0일 때는, 경우의 수가 0이 될 것이고, 무조건 isAdaptor의 친구 한명이랑 연결되어있어야합니다. 

따라서 DFS탐색을 1가지 경우 isAdaptor가 1인 경우를 다시 탐색을 시작합니다.

 

재귀를 호출하면서 구했던 경우의 수들을 누적해서 반환하여 다시 누적해서 최종 반환하면, 위의 문제에서 요구하는 얼리아답터가 최소가 되는 경우의 수를 구할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX = 1000001;

vector<int> node[MAX];
vector<int> tree[MAX];
int dp[MAX][2];

int n;

int adaptor(int root, int isAdaptor){
    if (tree[root].empty()){ 
        if (isAdaptor) return 1;	// 리프노드이고 isAdaptor일 때 1가지 경우의 수 반환
        else return 0;				// 리프노드이고 얼리아답터가 아닐 때 가지수는 0
    }

    int &ret = dp[root][isAdaptor];
    if (ret != -1) return ret; 		// 이미 계산한 값이 존재하다면, 해당 값 반환
    
    if (isAdaptor){					// 해당 노드가 얼리아답터라면
        ret = 1;					// 경우의 수 1 대입
        for (auto c: tree[root]){
            ret += min(adaptor(c, 1), adaptor(c, 0));	// 다음 탐색 노드가 얼리아답터일때와, 아닐 때 두가지중에서 최솟값을 누적시킴
        }
    } else{							// 해당 노드가 얼리아답터가 아님
        ret = 0;					// 경우의 수는 0
        for (auto c: tree[root]){
            ret += adaptor(c, 1);	// 다음 탐색 노드는 무조건 얼리아답터가 되어야한다. 
        }

    }

    return ret;						// 해당 노드의 경우수의 탐색된 노드의 누적된 경우의 수를 반환
}

void makeTree(int child, int parent){
    if (parent != 0) tree[parent].push_back(child); // 트리의 root가 아닐 때 해당 부모에 자식을 넣어준다.

    for (auto n: node[child]){
        if (n == parent) continue; // 부모를 다시 만날 경우 무시한다.
        makeTree(n, child); // 해당 노드에 있는 자식을 다시 탐색한다.
    }


}

void solution(){
    cin >> n;

    memset(dp, -1, sizeof(dp));

    for (int i = 0; i < n - 1; i++){

        int from, to;

        cin >> from >> to;

        node[from].push_back(to); // 우선 양방향 간선으로 만들어주기
        node[to].push_back(from); // 우선 양방향 간선으로 만들어주기
    }

    makeTree(1, 0); // 부모 1일부터 내려가면서 단방향 트리로 다시 만들어주기


    cout << min(adaptor(1, 1), adaptor(1, 0)) << '\n';
}
int main(){


    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();    
    
    return 0;
}