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

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

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

문제

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

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

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

 

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

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

 

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

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

입력

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

출력

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

---

풀이

처음에는 단순히 1번 root에서부터 얼리 어답터인 경우 / 얼리 어답터가 아닌 경우를 구분하며 모든 경우의 수를 조사해야 하는 줄 알았다. 

예제 입력 1을 보았을 때 그림이다.

부모가 얼리 어답터인 경우에는 자식은 얼리 어답터일 수도 있고 아닐 수도 있기 때문에 left, right에 각각 true와 false를 insert하였고,

부모가 얼리 어답터가 아닌 경우에는 자식은 반드시 얼리 어답터여야 하기 때문에 left에 true를 insert하였다.

 

하지만 당연하게도 위 풀이는 메모리 초과가 발생하였다. (아마 시간 초과도 발생할 것이다)

이에 조금 더 그리디적으로 문제를 접근하여 시간을 줄이고자 하였다.

 

핵심 아이디어는 '리프 노드는 얼리 어답터일 필요가 없다'와

'자식 노드들 중 하나라도 얼리 어답터가 아니라면 본인은 반드시 얼리 어답터이다' 두 가지이다.

리프 노드가 얼리 어답터라 하더라도 리프 노드의 부모는 자식들 모두가 얼리 어답터여야만 얼리 어답터가 아닐 수 있다.

설사 리프 노드의 부모의 자식이 1개라 할지라도 리프 노드의 부모의 부모까지 생각한다면 리프 노드의 부모가 얼리 어답터인 경우가 이득일 수밖에 없고 리프 노드가 얼리 어답터이지 않은 것이 이득이다.

 

따라서 리프 노드에서부터 얼리 어답터 유무를 조사하며 루트까지 올라온다면 답을 쉽게 구할 수 있다.

 

 

먼저 7, 8, 9는 리프 노드이기 때문에 얼리 어답터일 필요가 없다. 그리고 7, 8, 9를 자식으로 갖는 4는 반드시 얼리 어답터여야 한다. 그리고 4를 자식으로 갖는 2는 자식이 얼리 어답터이기 때문에 얼리 어답터일 필요가 없다.

다음으로 5, 6은 리프 노드이기 때문에 얼리 어답터일 필요가 없다. 그리고 5, 6을 자식으로 갖는 3은 반드시 얼리 어답터여야 한다.

마지막으로 2, 3을 자식으로 갖는 1은 2가 얼리 어답터가 아니기 때문에 얼리 어답터여야 한다.

물론 위 예제의 정답은 (1, 3, 4)뿐만 아니라 (2, 3, 4) 등이 존재한다. 하지만 위 아이디어를 통해 구한 인원보다 더 적은 인원만으로 조건을 만족하는 경우는 없었다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int n;
vector<int> graph[1000001];
int visited[1000001];
int answer = 0;

bool dfs(int pos){
    // 방문 처리
    visited[pos] = true;

    bool mustEarlyAdapter = false;
    for (int i = 0; i < graph[pos].size(); i++){
        int next = graph[pos][i];
        if (!visited[next]){
            // 자식이 얼리 어답터가 아니라면
            if (!dfs(next)){
                mustEarlyAdapter = true;
            }
        }
    }
    // 반드시 얼리 어답터여야 하는 경우
    if (mustEarlyAdapter){
        answer++;
        return true;
    }
    else{
        return false;
    }
}

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

    int n;
    cin >> n;

    for (int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1);
    cout << answer;

}