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

www.acmicpc.net/problem/2533

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

 

 

 

알고리즘 종류

트리

다이나믹 프로그래밍 (DP)

 

 

 

사고 과정

우선순위 큐를 이용해서 시도를 해봤지만, 해결할 수 없었습니다. 이 분의 블로그를 통해서 도움을 얻을 수 있었습니다. 그러나 어떻게 DP를 사용할 생각을 떠올렸는지는 알 수가 없었습니다. 이후에 다시 보고 해결해 보겠습니다. 이 문제를 보고 왜 DP로 풀어야 하는지 알 수 있었습니다. 트리의 독립집합 문제 유형으로 DP로 풀 수 있었습니다.

 

문제에서 제시된 조건은 아래와 같다.

    - 얼리 어답터가 아니면, 모든 친구들이 얼리 어답터야 한다.

    - 얼리 어답터이면, 주변 친구들이 얼리 어답터거나 아니어도 된다.

 

DP를 사용하는 방법을 이미지로 보여주면 아래와 같습니다.

 

Leaf에서 시작해서 '본인이 얼리 어답터일 때' 그리고 '본인이 얼리 어답터가 아닐 때' 주변의 얼리 어답터의 최소 개수를 DP에 저장합니다. 그렇게 Root까지 올라가면서 DP에 저장하게 되면, DP[1][0] 과 DP[1][1]에 트리를 모두 거친 얼리 어댑터의 최소 개수를 저장할 수 있습니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
 
int dp[1000001][2]; // 본인 노드가 얼리 일 때 또는 얼리가 아닐 때, 최소 얼리어댑터의 개수  
vector<vector<int> > edges;
vector<int> isVisited;
 
void dfs(int node){
    isVisited[node] = 1;
    dp[node][0] = 0; // 본인이 얼리가 아니면 얼리 개수 0 
    dp[node][1] = 1; // 본인이 얼리면 얼리 개수 1 
    
    for(int i=0; i<edges[node].size(); i++){
        int conn_node = edges[node][i]; 
        
        if(isVisited[conn_node]) continue; // 아래로 DFS 진행하기 위해서 위로 이동 방지  
        
        dfs(conn_node);
        
        dp[node][0] += dp[conn_node][1]; // 현재 노드가 얼리가 아니라면, 주변 노드는 얼리어야 한다. 
        dp[node][1] += min(dp[conn_node][0], dp[conn_node][1]); // 현재 노드가 얼리라면, 주변은 얼리 또는 얼리가 아니다. 
    }
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    edges.resize(n+1);
    isVisited.resize(n+1);
    
    int u, v;
    for(int i=1; i<n; i++){
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    
    dfs(1);
    
    cout << min(dp[1][0], dp[1][1]);
}

 

 

 

시행착오

본인이 처음 사용한 방법은 아래와 같습니다.

    1. 각 노드들이 주변 노드와 연결된 개수를 배열 arr 에 저장합니다.

    2. 노드 중에서 가장 많이 연결된 노드 A를 우선순위 큐로 찾습니다. 가장 영향력있는 인플루언서 입니다.

    3. A와 연결된 다른 노드들의 노드 연결 개수를 arr에서 -1씩 감소시킵니다. A를 제거했으니 연결을 끊습니다.

    4. 2번과 3번을 반복합니다.

 

위 방법으로 하니 시간복잡도가 n*n*logn이라서 시간초과가 발생했습니다. 그럼에도 불구하고, 시도는 해보고 배울 것이 있을 것이라고 생각했기 때문입니다.

 

시도했던 코드는 아래에 있습니다.

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int n;
 
vector<vector<int> > edges;
vector<int> nodes;
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    edges.resize(n+1);
    nodes.resize(n+1);
    
    int u, v;
    for(int i=0; i<n-1; i++){
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
        
        nodes[u]++;
        nodes[v]++;
    }
    
    int cnt=0;
    while(true){
        priority_queue<pair<int, int> > pq;
        
        for(int i=1; i<=n; i++){
            if(nodes[i] <= 0) continue;
            pq.push({nodes[i], i});
        }
        
        if(pq.empty()) break;
    
        int node = pq.top().second;
        nodes[node] = 0;
        cnt++;
        
        for(int i=0; i<edges[node].size(); i++){
            int next_node = edges[node][i];
            nodes[next_node]--;
        }
 
    }
    
    cout << cnt << endl;
    
}