[백준 2533번] Dynamic Programming으로 풀어보기 : Programming Story

1. 문제

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

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

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

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

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

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

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

1) 입력

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

2) 출력

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

2. 풀이

이 문제에서는 한 사람마다 두 가지 상태가 가능하다. early adopter일 수도 있고, 그렇지 않을 수도 있는 것이다.

따라서 우리는 dp[][] 라는 2차원 배열을 만들고

dp[ id ] [0] 에는 id번째 사람이 early adopter가 아닐 경우에 필요한 early adopter의 명수를 저장하고

dp[ id ] [1] 에는 id번째 사람이 early adopter일 경우에 필요한 early adopter의 명수를 저장할 것이다.

그리고 문제에서 tree의 구조를 제시했기 때문에 tree의 하단으로 내려가면서 dp의 배열을 채우가는 식으로 구상을 했기 때문에 DFS 알고리즘의 방식을 차용했다고 볼 수 있을 것 같다.

점점 tree의 말단으로 내려가야 하기 때문에 visit이라는 boolean 배열을 하나 만들고 해당 node가 방문되었는지를 체크한다.

또한 이 문제 다이나믹 프로그래밍의 핵심이 되는 부분은 아래와 같다.

dp[cur][0]+=dp[next][1];
dp[cur][1]+=Math.min(dp[next][0], dp[next][1]);

1) 현재 방문되고 있는 node의 사람이 early adopter가 아닐 경우 (dp[cur][0])

이 경우, 반드시 자신과 인접한 자식 node가 early adopter이여야 하기 때문에 dp[next][1]의 개수를 더한다. 그리고 tree의 계층 구조를 나타내기 위해, 그리고 자신의 parent node의 개수를 중복으로 더하지 않기 위해 우리는 visit이라는 배열을 사용하여 tree의 아래로만 계속 내려가는 알고리즘을 구현할 수 있는 것이다.

2) 현재 방문되고 있는 node의 사람이 early adopter일 경우 (dp[cur][1])

이 경우 자신과 인접한 자식이 early adopter이든, 아니든 큰 관계가 없다. 이 경우 반드시 자식 node가 early adopter가 아니어야 한다고 생각하면 틀린 생각이다. 전체 tree 구조에서 early adopter 합계의 minimum을 구하는 것이기 때문에 자식 노드가 early adopter인 경우가 오히려 최소가 될 수도 있다. 따라서 자식 노드가 early adopter일 경우와 그렇지 않을 경우의 minimum을 더해주어야 한다.

3. 코드

Java로 구현한 전체 코드는 아래와 같다.

import java.util.*;
import java.io.*;

public class Main{
    static boolean visit[];
    static ArrayList<Integer> arr[];
    static int dp[][];
    static void dfs(int index){
        visit[index]=true;
        dp[index][0]=0; //index가 early adopter가 아닐 경우
        dp[index][1]=1; //early adopter일 경우
        for(int next: arr[index]){
            if (!visit[next] ){
                dfs(next);
                dp[index][0]+=dp[next][1];
                dp[index][1]+=Math.min(dp[next][0], dp[next][1]); 
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        visit=new boolean[n+1];
        arr=new ArrayList[n+1];
        dp=new int[n+1][2];
        for(int i=1; i<=n; i++){
            arr[i]=new ArrayList<>();
        }
        for(int i=0; i<n-1; i++){
            String infos[]=br.readLine().split(" ");
            arr[Integer.parseInt(infos[0])].add(Integer.parseInt(infos[1]));
            arr[Integer.parseInt(infos[1])].add(Integer.parseInt(infos[0]));
        }
        dfs(1);
        System.out.println(Math.min(dp[1][0], dp[1][1]));
    }
}

여기서 꼭 tree의 root가 1일 필요는 없다. 다른 것을 시작 index로 설정해도 무방하나 마지막에 print되는 노드도 일관되게 같은 index의 값을 살펴보면 된다.