[백준 - 2533][Gold 3] - 사회망 서비스(SNS) (JAVA)

문제 링크

---

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가 하나의 빈칸을 사이에 두고 주어진다. 

 

출력

---

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

 

단순 구현으로 풀릴까?

---

우선 가장 쉬운 방법인 구현을 생각해보자.

 

각 친구별로 얼리억세스인 경우와 아닌경우의 조합을 구해서 해당 경우가 가능한지 판단한 후 모든 사람이 얼리어답터를 받아들이는지 확인하면 문제를 해결할 수 있을 것이다. 이에 대한 시간복잡도를 구하면 다음과 같다.

 

O(N)
= (친구가 얼리억세서인 경우 or 아닌경우) * (모든 친구가 얼리억세스를 받아들이는지 탐색)
= 2^N * N

 

N은 최대 1,000,000이므로 위의 방법으로 문제를 풀면 예상 연산 횟수는 최대 2^ 1,000,000 * 1,000,000 이다. 이는 제한시간 3초의 예상 연산 횟수인 3억보다 훨신 큰 횟수이므로 위의 방법으로는 문제를 풀 수 없다. 다른 방법을 생각해보자.

 

DP로 해결할 수 있을까??

---

최소 횟수를 구하는 알고리즘은 DP로 생각해보자.

 

한 친구와 다음 친구에 영향을 끼치는 경우의 수를 모두 구해보면 다음과 같다.

 

• 현재 친구가 얼리억세서가 아닌 경우
  • 다음 친구가 얼리억세서야 현재 친구가 얼리억세서를 받아들인다.
• 현재 친구가 얼리억세서인 경우
  • 다음 친구가 얼리억세서거나 아니어도 현재 친구는 얼리억세서를 받아들인다.

 

만약 현재 친구가 얼리억세서가 아니면 다음 친구는 모두 얼리억세서여야 현재 친구와 다음 친구들이 얼리 억세서를 받아들일 수 있다.

 

만약 현재 친구가 얼리억세서라면 다음 친구가 얼리억세서던 아니던 현재 친구와 다음 친구들은 모두 얼리억세서를 받아들인다. 그러므로 다음 친구가 무조건 얼리억세서여야 되는 경우의 수만 더하면 되므로 다음 친구가 얼리억세서인 경우와 아닌경우의 합의 최소값이 현재 친구까지의 관계의 최소 얼리억세서 수가 될 것이다.

 

이를 점화식으로 표현하면 다음과 같다.

 

최소 얼리 억세서의 수 [현재 친구][얼리억세서임] = SUM(MIN(최소 얼리억세서의 수 [다음 친구][얼리억세서 아님], 최소 얼리억세서의 수 [다음 친구][얼리억세서 임]))

최소 얼리 억세서의 수 [현재 친구][얼리억세서 아님] = SUM(최소 얼리억세서의 수 [다음 친구][얼리억세서 임])

 

위의 점화식을 응용하여 DP로 해결했을 때 시간복잡도를 구하면 다음과 같다.

 

O(N) = (친구의 수) * (얼리억세서인 경우 or 아닌 경우)
= N * 2

 

N은 최대 1,000이므로 위의 방법으로 문제를 풀면 예상 연산 횟수는 최대 2 * 1,000,000이다. 이는 제한시간 3초의 예상 연산 횟수인 3억보다 작기 때문에 해결할 수 있다!

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    final static int TRUE = 1;
    final static int FALSE = 0;
    static boolean[] visited;
    static List<Integer> graph[];
    static int[][] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        graph = new ArrayList[N+1];
        visited = new boolean[N+1];
        dp = new int[N+1][2];

        for(int i=0;i<=N;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0;i<N-1;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            graph[from].add(to);
            graph[to].add(from);
        }

        findCount(1,TRUE);

        System.out.println(Math.min(dp[1][TRUE],dp[1][FALSE]));
    }

    public static int findCount(int curr,int valid){
        if(visited[curr]){
            return dp[curr][valid];
        }
        visited[curr] = true;

        dp[curr][TRUE] = 1;
        dp[curr][FALSE] = 0;

        for(int next : graph[curr]){
            if(visited[next]){
                continue;
            }
            int nextTrue = findCount(next, TRUE);
            int nextFalse = findCount(next, FALSE);

            dp[curr][FALSE] += nextTrue;
            dp[curr][TRUE] += Math.min(nextTrue,nextFalse);
        }

        return dp[curr][valid];
    }
}

 

 

실행 결과

---

 

 

제한시간인 3초안에 문제가 해결되었다!

 

키워드

---

• 최소 얼리 어답터의 수
  • 완전탐색, DP, 그리디

 

 

팁

---

 

• DP로 풀고 싶다면 경우의 수의 조건을 모두 따져 DP 배열을 만들어보고 시간 복잡도를 계산해 가능한지 판단해보자.
• Top-Bottom방식으로 생각나지 않는다면 재귀를 통한 Bottom-Top 방식도 생각해보자