[백준] 사회망 서비스(SNS) (tree DP)

문제 소개

백준 2533번 사회망 서비스(SNS) 문제 정리합니다.

이 문제는 친구 관계가 트리로 주어졌을 때 최소 얼리 어답터 수를 구하는 문제입니다.

핵심은 각 노드의 상태(얼리 어답터 여부)에 따른 최적값을 DP로 계산하는 데 있습니다.

문제 링크: 사회망 서비스(SNS) - 백준 2533번

---

 

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 문제 조건 분석: 얼리 어답터가 아닌 사람은 모든 친구가 얼리 어답터여야 함
2. 그래프 특성 - 트리: 친구 관계가 트리 구조로 주어짐 (사이클 없음)
3. 완전탐색의 한계: 각 사람마다 2가지 선택(얼리 어답터 O/X)이 있으므로 2^N은 시간초과
4. 분할정복 아이디어: 부모 노드의 답 = 자식 노드들의 답을 조합해서 구할 수 있음
   • 부모가 얼리 어답터면: 자식은 어떤 상태든 OK → min(자식이 얼리 어답터 아닌 경우, 자식이 얼리 어답터인 경우) 선택
   • 부모가 얼리 어답터 아니면: 모든 자식이 얼리 어답터여야 함 → 자식이 얼리 어답터인 경우 강제 선택
5. DP 상태 정의: dp[node][0/1] = node가 얼리 어답터 아닌(0)/인(1) 경우의 최적해
6. 트리 DP 적용: 리프부터 시작해서 부모로 올라가며 최적값 전파

---

해결 과정 및 코드

핵심 아이디어

1. DP 상태 정의: 각 노드에 대해 2가지 경우로 나누어 계산
   • dp[node][0]: node가 얼리 어답터가 아닌 경우의 최소값
   • dp[node][1]: node가 얼리 어답터인 경우의 최소값
2. 점화식: 자식들의 DP 값을 이용해 부모 계산
   • dp[node][0] = sum(dp[child][1]) (모든 자식이 얼리 어답터)
   • dp[node][1] = 1 + sum(min(dp[child][0], dp[child][1])) (자식은 자유)
3. DFS 순회: 리프 노드부터 계산하는 Post-order 방식 사용
4. 임의 루트: 트리이므로 아무 노드나 루트로 설정해도 답은 동일

---

코드

시간 복잡도: O(N) - 각 노드를 한 번씩만 방문

공간 복잡도: O(N) - DP 테이블과 인접 리스트

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

public class Main {
    static ArrayList<Integer>[] adj; // 인접리스트 - 그래프(트리)
    static int[][] dp;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        int n = read();
        // 인접 리스트 초기화
        adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
        // 간선 정보 입력 (무방향 그래프)
        for (int i = 0; i < n - 1; i++) {
            int u = read(), v = read();
            adj[u].add(v); adj[v].add(u);
        }

        // DP 테이블과 방문 배열 초기화
        dp = new int[n + 1][2];
        visited = new boolean[n + 1];
        // 1번 노드를 루트로 하여 DFS 실행
        dfs(1);
        // 루트가 얼리 어답터인 경우와 아닌 경우 중 최소값 출력
        System.out.println(Math.min(dp[1][0], dp[1][1]));
    }

    static void dfs(int node) {
        visited[node] = true;
        // 초기값 설정
        dp[node][0] = 0; // node가 얼리 어답터가 아닌 경우
        dp[node][1] = 1; // node가 얼리 어답터인 경우 (자기 자신 포함)

        // 모든 자식 노드에 대해 재귀적으로 계산
        for (int child : adj[node]) {
            if (visited[child]) continue; // 이미 방문한 노드 제외

            dfs(child); // 자식 노드 먼저 계산 (Post-order)

            // node가 얼리 어답터가 아니면, 모든 자식은 얼리 어답터여야 함
            dp[node][0] += dp[child][1];
            // node가 얼리 어답터이면, 자식은 얼리 어답터이거나 아니거나 상관없음
            dp[node][1] += Math.min(dp[child][0], dp[child][1]);
        }
    }

    // 빠른 입력을 위한 read 함수
    public static int read() throws IOException {
        int cur, n = System.in.read() & 15;
        boolean isNegative = (n == 13);
        if (isNegative) n = System.in.read() & 15;
        while ((cur = System.in.read()) > 32) n = (n << 3) + (n << 1) + (cur & 15);
        return isNegative ? -n : n;
    }
}

---

트리 DP 개념 정리

트리 DP란?
트리 구조에서 노드의 상태를 기반으로 동적 계획법을 적용하는 기법입니다.

트리 DP의 특징:

• Post-order 순회: 자식부터 계산하여 부모로 전파
• 상태 분할: 각 노드의 가능한 상태들을 나누어 최적값 계산
• 무사이클: 트리 구조라 중복 계산 없이 DP 적용 가능

문제에서의 적용:

dp[node][0] = Σ dp[child][1]           // node가 얼리 어답터 아님
dp[node][1] = 1 + Σ min(dp[child][0], dp[child][1])  // node가 얼리 어답터

DFS를 사용하는 이유:

• 자연스러운 Post-order: 재귀로 자식을 먼저 처리
• 코드 간결성: 복잡한 위상정렬 구현 불필요
• 메모리 효율: 추가 자료구조 없이 재귀 스택만 사용