[BOJ] 2533번 - 사회망 서비스(SNS)

백준 2533번 - 사회망 서비스(SNS)

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초	256 MB	10408	3838	2477	34.917%

문제

페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다.

예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 

친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adaptor)라고 하는데, 사회망 서비스에 속한 사람들은 얼리 아답터이거나 얼리 아답터가 아니다. 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 

어떤 아이디어를 사회망 서비스에서 퍼뜨리고자 할 때, 가능한 한 최소의 수의 얼리 아답터를 확보하여 모든 사람이 이 아이디어를 받아들이게 하는  문제는 매우 중요하다. 

일반적인 그래프에서 이 문제를 푸는 것이 매우 어렵다는 것이 알려져 있기 때문에, 친구 관계 그래프가 트리인 경우, 즉 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우만 고려한다. 

예를 들어, 8명의 사람으로 이루어진 다음 친구 관계 트리를 생각해보자. 2, 3, 4번 노드가 표현하는 사람들이 얼리 아답터라면, 얼리 아답터가 아닌 사람들은 자신의 모든 친구가 얼리 아답터이기 때문에 새로운 아이디어를 받아들인다.

친구 관계 트리가 주어졌을 때, 모든 개인이 새로운 아이디어를 수용하기 위하여 필요한 최소 얼리 어답터의 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에지 (u, v)를 나타내는 두 정수 u와 v가 하나의 빈칸을 사이에 두고 주어진다. 

출력

주어진 친구 관계 그래프에서 아이디어를 전파하는데 필요한 얼리 아답터의 최소 수를 하나의 정수로 출력한다.

---

예제 입력 1

8
1 2
1 3
1 4
2 5
2 6
4 7
4 8

예제 출력 1

3

예제 입력 2

9
1 2
1 3
2 4
3 5
3 6
4 7
4 8
4 9

예제 출력 2

3

출처

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

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

알고리즘 분류

• 다이나믹 프로그래밍
• 트리
• 트리에서의 다이나믹 프로그래밍

접근 방법

일반적인 완전탐색으로는 시간초과로 해결할 수 없는 문제이다. 

트리 형태로 친구관계가 주어졌을 때, 모든 개인이 아이디어를 수용할 수 있도록 조건을 만족하는 최소의 얼리 아답터의 수를 구하기 위해

다음과 같이 메모이제이션 배열을 설정해주자.

dp[i][?] = i를 루트 노드로 하는 Sub-Tree의 최소 얼리 어답터의 수

1. dp[i][NORMAL] = i를 루트노드로 하고 i노드는 얼리 어답터가 아닐 때, sub-tree의 최소 얼리 아답터의 수
2. dp[i][EARLY_ADOPTER] = i를 루트노드로 하고 i노드는 얼리 어답터일 때, sub-tree의 최소 얼리 아답터의 수

다음과 같이 테이블을 정의할 경우에 dp[i][NORMAL] 은 인접한 노드들(=트리에서 자식노드)이 전부 얼리 아답터여야만 하므로, dp[child][EARLY_ADOPTER] 일 때 값을 전부 더해준다. 

dp[i][EARLY_ADOPTER] 일 경우에, 인접한 노드들은 얼리 아답터 일수도 아닐 수도 있으므로 각각의 경우의 최소값을 더해준다.

마지막으로 i노드도 얼리 아답터 이므로 +1을 해주므로서 dp테이블을 전부 채울 수 있다.

 

트리 형태의 양방향 그래프를 단방향성 임의의 트리로 만드는 함수 - makeAdj 

먼저, 주어진 그래프는 문제 조건에 따라 트리 형태를 만들 수 있는 그래프이다.

친구 관계 트리의 에지 (u, v)에 방향성이 나타나 있지 않으므로, 기본적으로 양방향성을 갖는다고 설정해준다.

이것을 다시 트리로 치환하는 것이 중요한데, 루트노드를 무엇을 잡느냐에 따라 트리의 형태가 바뀔 수 있다.

하지만, 우리가 풀고자하는 문제에서 임의의 한 정점을 루트 노드로 잡는다고 해서 트리의 특성이 깨지지 않고 또한 각 정점들 간의 위상관계가 중요하지 않으므로 아무 점이나 최상위 루트 노드(${Top_{node}}$)로 잡아도 무방하다.

단, 우리가 만든 트리의 최상위 루트노드에서 부터 DFS를 수행하며 dp table을 채워나갈 것이기 때문에 탐색 순서를 보장하기 위해 앞에서 잡은 ${Top_{node}}$ 부터 탐색을 해야한다는 점만 주의하면 되겠다.

 

소스 코드

#define NORMAL 0
#define EARLY_ADOPTER 1
#include <bits/stdc++.h>
using namespace std;
int N, dp[1000001][2];
vector<int> in[1000001], adj[1000001];
void makeAdj(int current, int prev){
    for(auto next : in[current]){
        if( next != prev ){
            adj[current].push_back(next);
            makeAdj(next, current);
        }
    }
}
int findAns(int current, int type){
    int& ret = dp[current][type];
    if( ret != -1 )
        return ret;
    if( adj[current].empty() ){
        // leaf 노드일 때
        return dp[current][type] = type;
    }
    if( type == NORMAL ){
        ret = 0;
        for(auto next : adj[current]){
            ret += findAns(next, EARLY_ADOPTER);
        }
    }
    else if( type == EARLY_ADOPTER ){
        ret = 1;
        for(auto next : adj[current]){
            ret += min( findAns(next, EARLY_ADOPTER), findAns(next, NORMAL) );
        }
    }
    return ret;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> N;
    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        in[a].push_back(b);
        in[b].push_back(a);
    }

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

    // top -> bottom
    cout << min( findAns(1, 0), findAns(1, 1) ) << '\n';
    return 0;
}