[백준/BOJ] 2533번 : 사회망 서비스(SNS) (DP)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 2533번 : '사회망 서비스(SNS)' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold III에 해당하며, 문제를 풀이하기 위해 DP의 응용에 대한 이해가 필요합니다.

 

 

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

 

주어진 그래프에 대해 선택된 노드를 포함하여 1개의 간선을 통해 인접한 노드들까지 선택한다고 할 때, 모든 노드를 선택되게 하기 위해서는 최소 몇 개의 노드를 지정해야 하는지를 구하는 문제입니다.

 

가장 쉽게 떠올릴 수 있는 풀이는 DP를 이용하여, 가장 말단 노드부터 재귀적으로 하위 노드들을 모두 선택되게 하기 위해 몇 개의 노드를 지정해야 하는지를 기록해오면서 root 노드까지 계산해오는 것입니다.

 

DP를 이용하여 위의 아이디어를 풀이로 구현해보겠습니다.

 

 

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

bool visited[MAX];
int dp[MAX][2] = {};
vector<int> edge[MAX], child[MAX];

void findChild(int node) {
    visited[node] = true;
    for(int i=0; i<edge[node].size(); i++) {
        int next = edge[node][i];
        if(!visited[next]) {
            child[node].push_back(next);
            findChild(next);
        }
    }
}

int recordDP(int node, bool isEA) {
    if(dp[node][isEA] != 0) return dp[node][isEA];
    if(child[node].size() == 0) return dp[node][isEA] = isEA;
    if(isEA) {
        int ans = 0;
        for(int i=0; i<child[node].size(); i++) {
            int next = child[node][i];
            ans += min(recordDP(next, true), recordDP(next, false));
        }
        return dp[node][isEA] = ans + 1;
    }
    else {
        int ans = 0;
        for(int i=0; i<child[node].size(); i++) {
            int next = child[node][i];
            ans += recordDP(next, true);
        }
        return dp[node][isEA] = ans;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    for(int i=0; i<N-1; i++) {
        int u, v; cin >> u >> v;
        edge[u].push_back(v), edge[v].push_back(u);
    }
    findChild(1);
    cout << min(recordDP(1, true), recordDP(1, false));
}

 

우선 이 문제에서는 트리 그래프에서 노드와 노드 사이의 연결 관계만 주어졌을 뿐 노드의 상하위 관계가 입력으로 주어지지 않았으므로, 1번 노드를 그냥 root 노드로 잡고 각 노드들의 child들을 vector에 저장해주도록 합니다.

위의 코드에서는 findChild 함수가 이를 수행하고 있습니다.

 

이제 dp를 정의해야 하는데, 각 노드는 문제에서 말하는 얼리어답터(Early Adapter, EA)로 선택하거나 선택하지 않을 수 있으므로, dp[node][isEA]를 (node)번 노드를 EA로 지정했거나(isEA = 1) 지정하지 않은 경우(isEA = 0) 하위 노드들을 모두 선택되도록 하는 최소 EA의 수를 의미하도록 정의합니다.

 

이제 재귀적으로 dp를 기록할 수 있도록 recordDP 함수를 작성해줍니다.

하위 노드의 dp 값이 이미 계산된 경우 dp != 0이므로 이 경우는 그냥 dp 값을 반환해주도록 합니다.

child 노드가 없는 경우 해당 노드의 dp 값은 isEA인 경우는 해당 노드를 선택한 것이 전부이므로 1, 그 외의 경우는 0을 반환해주도록 합니다. (즉, 그냥 isEA 값을 반환해주면 됩니다.)

 

dp 값을 계산하려는 노드가 isEA = 1인 경우 하위 노드를 EA로 지정한 경우와 그렇지 않은 경우 모두 dp 값을 계산한 뒤 둘 중 더 작은 값을 선택하고, 현재 노드를 EA로 선택했으므로 1을 더해서 return 해줍니다.

반대로 dp 값을 계산하려는 노드의 isEA = 0인 경우에는 하위 노드를 반드시 선택해야만 현재 노드 역시 EA의 인접 노드로 선택이 될 수 있으므로 min이 아닌 그냥 child 노드의 isEA = 1로 지정해서 dp 값을 재귀적으로 계산해주면 됩니다.

 

최종적으로 구해야되는 값은 root 노드가 EA로 지정된 경우와 그렇지 않은 경우의 dp 값의 최솟값이므로, min(recordDP(1, true), recordDP(1, false)) 값을 출력해주면 됩니다.

 

 

 

위와 같이 풀이를 작성하여 제출하면, 1초가 넘는 시간이 소요되고 정답 처리를 받을 수 있습니다.

(16일 전에 제출한 풀이인데 괜찮은 DP 문제인 것 같아서 이제서야 포스트를 작성합니다.)