[BOJ][Java] 2533. 사회망 서비스(SNS)

문제

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

 

문제 이해

• SNS 네트워크는 트리(사이클 없음) 로 주어진다.
• 어떤 사람이 정보를 전달받으려면 그 사람의 이웃 중 적어도 한 명은 ‘얼리어답터’ 여야 한다.
• 모든 사람이 정보를 전달받도록 할 때, 필요한 얼리어답터의 최소 수를 구한다.

TIP: “모든 간선마다 양 끝점 중 최소 한 쪽은 선택되어야 함” 이라고 생각하면 이해하기 쉽다.

 

풀이 아이디어: 트리 DP

루트를 1로 잡고 DFS로 트리를 내려가며 탐색한다.

 

상태 정의

• dp[0][node] : node가 얼리어답터가 아닐 때, node의 서브트리에서 필요한 최소 얼리어답터 수
• dp[1][node] : node가 얼리어답터일 때, node의 서브트리에서 필요한 최소 얼리어답터 수

 

점화식

현재 정점을 cur, 자식 정점을 child라 할 때, 모든 간선 (cur, child) 에서 최소 한 쪽은 얼리어답터로 선택되어야 한다.

1. cur가 얼리어답터가 아닌 경우
   → child는 반드시 얼리어답터여야 한다.

dp[0][cur] = Σ dp[1][child]

(Σ : 각 자식 서브트리에서 얻은 dp값들을 더한다)

 

 

2. cur가 얼리어답터인 경우
   → 간선 (cur, child)는 이미 cur 쪽에서 만족. child는 얼리어답터일 수도/아닐 수도 있다. 더 작은 쪽을 선택한다.

dp[1][cur] = 1 + Σ min(dp[0][child], dp[1][child])

여기서 +1은 cur 자신이 얼리어답터인 것을 포함한다.

 

DFS 탐색

• dp[0][u] = 0, dp[1][u] = 1 로 두고 자식들을 반영해 누적한다. 정답은 min(dp[0][1], dp[1][1]) (루트 1 기준)
• 트리이므로 visited로 부모 재방문을 막아준다.

 

코드

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

public class Main {
    static int n;
    static List<Integer>[] graph;
    static boolean[] visited;
    static int[][] dp;

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

        n = Integer.parseInt(br.readLine());
        visited = new boolean[n + 1];
        graph = new ArrayList[n + 1];
        dp = new int[2][n + 1]; // [0]: 얼리어답터 X, [1]: 얼리어답터 O

        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 u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[u].add(v);
            graph[v].add(u);
        } // 입력 끝

        dfs(1);

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

    static void dfs(int cur) {
        visited[cur] = true;
        dp[0][cur] = 0;
        dp[1][cur] = 1;

        for (int child : graph[cur]) {
            if (visited[child])
                continue;

            dfs(child);
            dp[0][cur] += dp[1][child]; // 자식이 무조건 얼리어답터
            dp[1][cur] += Math.min(dp[0][child], dp[1][child]);
        }
    }
}