알고리즘 & BOJ 2533 사회망 서비스(SNS)(C++)

2574 : 사회망 서비스(SNS)

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 65 회    시도횟수: 547 회   

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

 

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

 

 

 

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

 

 

 

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

 

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

 

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

 

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

 

입력의 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2≤N≤1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다.

두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에지 (u,v)를 나타내는 두 정수 u와 v가 하나의 빈칸을 사이에 두고 주어진다.

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

[테스트데이터 조건]
• N이 500 이하인 테스트데이터가 전체의 40%이다.
• N이 10,000 이하인 테스트데이터가 전체의 60%이다.

[Copy] 8 1 2 1 3 1 4 2 5 2 6 4 7 4 8

[Copy] 3

[Copy] 9 1 2 1 3 2 4 3 5 3 6 4 7 4 8 4 9

[Copy] 3

출처 : KOI 본선 2012 중4

?

/**************************************************************
    Problem: 2574
    User: a132034
    Language: C++
    Result: Success
    Time:955 ms
    Memory:88400 kb
****************************************************************/
 
 
#include    <cstdio>
#include    <vector>
#include    <algorithm>
#pragma warning (disable : 4996)
 
struct tree
{
    int rank;
    int none, early;
    std::vector<int> ad_vertex;
};
int q[1111111];
int st[1111111];
int visit[1111111];
tree t[1111111];
int top = 0;
int front = 0, rear = 0;
 
int main()
{
    int N;
    scanf("%d", &N);
    if (N == 1)
    {
        printf("1");
        return 0;
    }
    int v, u;
    for (int i = 1; i < N; ++i)
    {
        scanf("%d%d", &v, &u);
        t[v].ad_vertex.push_back(u);
        t[u].ad_vertex.push_back(v);
    }
    int T = 1; //루트노드 
               //BFS
    int r = 1;
    visit[T] = 1;
    st[++top] = T;
    q[++rear] = T; //루트 노드 
    while (front <= rear)
    {
        int node = q[++front];
        t[node].rank = r++; //탐색하여 탐색우선순위 지정. 
        for (std::vector<int>::iterator it = t[node].ad_vertex.begin(); it != t[node].ad_vertex.end(); ++it)
        {
            if (visit[*it] != 1) //방문하지 않았다면 
            {
                visit[*it] = 1;
                q[++rear] = *it;
                st[++top] = *it;
            }
        }
    }
    for (int i = top; i > 0; --i)
    {
        int index = st[i];
        t[index].none = 0;
        t[index].early = 1;
        for (int j = 0; j < t[index].ad_vertex.size(); ++j)
        {
            int chlidIdx = t[index].ad_vertex[j];
            t[index].none += t[chlidIdx].early;
            t[index].early += std::min(t[chlidIdx].early, t[chlidIdx].none);
        }
    }
    printf("%d", std::min(t[T].none, t[T].early));
    return 0;
}

BOJ 링크 dynamic programming 문제.  기존에 풀던 다이나믹보다 조금 더 어렵고 새로운 유형의 문제였다.  바로 트리를 이용한 다이나믹 문제.  모두 새로운 아이디어를 수용하도록 만들기 위해서 두 가지로 나누어 해답을 생각할 수 있다.  1. 자신이 얼리어답터인 경우 >> 나머지는 얼리어답터가 아니어도 된다.  2. 자신이 얼리어답터가 아닌 경우 >> 이웃한 모두가 얼리어답터여야 한다.  트리는 일반적으로  root node를 기점으로 트리가 있고  그 자식을 root node로 한 서브트리가 존재하는 구조로 이는 작은 트리(작은 문제의 해답)를 이용하여 큰 트리(큰 문제의 해답)를 구성할 수 있는 구조이다.  다이나믹프로그래밍을 적용하기에 어렵지 않다.  root node를 기준으로  child node들이 있을 때  child node를 root node로 하는 서브트리 전체가 새로운 아이디어를 수용하도록 만들기 위한 최소 얼리어답터 수를  D[i]라고 한다. 이떄의 i는 서브트리의 root node 번호이다.  예를들어 아래와 같은 트리가 있을 때  1 2     3     4   5   D[1]은 1을 root node로 하는 아래와 같은 트리 전체를 문제의 조건인 새로운 아이디어를 수용하도록 만들기위한 최소 얼리어답터 수 이다.  D[2]는 2를 root node로 하는 2, 5라는 정점을 가진 트리에서 새로운 아이디어를 수용하도록 만들기위한 최소 얼리어답터 수 이다.  이럴 때  D[i]는 위의 경우처럼 두 가지로 나누어 생각할 수 있다.  1. D[i]가 얼리어답터일 경우 >>> i의 child node는 얼리어답터일 수도 있고 아닐 수도 있다. (두 경우 모두 가능) 2. D[i]가 얼리어답터가 아닐 경우 >>> i의 child node는 무조건 얼리어답터이어야 한다.  라고 한다면 각 정점에 대해 두가지 경우를 저장해야 한다는 것을 알 수 있다.  D[i][자신이 얼리어답터일 경우] 와 D[i][자신이 얼리어답터가 아닐 경우] 를 저장한다면  D[i]는 위에서 나눈 경우의 수를 이용하여 70~75라인처럼 구할 수 있다.  이 문제에 다이나믹 프로그래밍을 이용해 풀기 위해서는 작은 문제를 먼저 풀어야 한다.  작은 문제는 트리에서는 가장 아래쪽의 leaf node부터이므로 이 순서를 정해주어야 하는데  문제에서는 주어진 순서의 가장 처음이 root node이고 가장 마지막이 leaf node라는 보장이 없다.  그러므로 임의의 node를 root node로 설정한 후 dfs 혹은 bfs등을 이용하여 어떤 node부터 계산해야 할 지 순서를 정해주는 작업이 중요하다.  위의 코드에서는 1을 무조건 root node로 잡았고 bfs를 사용하였다.  bfs를 사용하며 방문한 정점을 차례로 스택에 넣었고 스택에서 빼면서 가장 작은 문제인 leaf node부터 차례대로 큰 트리순서로 풀었다.