[BOJ/DFS+DP] 백준 2533 - 사회망 서비스(SNS) (Java)

2533 - 사회망 서비스(SNS)

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

문제

사회망에서 사람들의 친구 관계 그래프로 표현 (사이클 X) 
(사람 -> 정점 / 두 사람이 서로 친구 관계 -> 정점을 잇는 에지)
-> 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정 이해

얼리 어답터(early adaptor): 어떤 새로운 아이디어를 먼저 받아들인 사람
/ 얼리 어답터가 아닌 사람은 자신의 모든 친구들이 얼리 어답터일 때만 이 아이디어 받아들임
=> 친구 관계 트리가 주어졌을 때 모든 개인이 새로운 아이디어를 수용하기 위해 필요한 최소 얼리 어답터 수?

입력
첫째 줄: 친구 관계 트리의 정점 개수 N (2 <= N <= 1,000,000, 각 정점 1 ~ N까지 일련번호로 표현)
두 번째 줄 N - 1개의 줄: 각 줄마다 친구 관계 트리의 에지(u, v) 나타내는 두 정수
출력: 아이디어 전파하는데 필요한 얼리 어답터의 최소 수

---

풀이

DFS + DP

• `dp[v][0]`: v가 얼리어답터 X -> 필요한 최소 얼리어답터 수
  • 자식 노드 반드시 얼리어답터야 함
    -> `dp[v][0] += dp[child][1]`
• `dp[v][1]`: v가 얼리어답터 O -> 필요한 최소 얼리어답터 수
  
  • 자식 얼리어답터이든 아니든 상관 X
    -> `dp[v][1] += min(dp[child][0], dp[child][1])`

-> 부모-자식 간의 의존 관계

/ 자식의 dp 먼저 계산해야 부모 dp 채울 수 있음 -> 후위 순회(DFS)

=> 트리 DP 패턴 = DFS 기반 하향식 DP

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

    for (int next : graph[v]) {
        if (!visited[next]) {
            dfs(next);
            dp[v][0] += dp[next][1];
            dp[v][1] += Math.min(dp[next][0], dp[next][1]);
        }
    }
}

---

코드

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

// 사회망 서비스(SNS)
public class boj_2533 {
    static int N;
    static List<Integer>[] graph;
    static int[][] dp;
    static boolean[] visited;

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

        for (int next : graph[v]) {
            if (!visited[next]) {
                dfs(next);
                dp[v][0] += dp[next][1];
                dp[v][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));

        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N + 1];
        for (int i = 1; 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);
        }

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

        dfs(1);

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