백준 - 사회망 서비스 (SNS)

다른 사람 풀이

import sys
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
readline = stdin.readline

N = int(input())
tree = [[] for _ in range(N+1)]
dp = [[0, 1] for _ in range(N+1)] # 0: 노드가 얼리어답터가 아닐때, 1: 얼리어답터 일 때
visited = [False] * (N+1)

for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    tree[u].append(v)
    tree[v].append(u)

def dfs(cur):
    visited[cur] = True
    for child in tree[cur]:
        if not visited[child]:
            dfs(child)

            # 현재 노드가 얼리어답터가 아니면 자식은 무조건 얼리어답터여야 한다.
            dp[cur][0] += dp[child][1]

            # 현재 노드가 얼리어답터일 경우 자식 노드는 얼리어답터여도 되고 아니여도 된다.
            dp[cur][1] += min(dp[child])

dfs(1)
print(min(dp[1]))

트리에서 dp를 활용하는 문제는 예전에 카카오에 나온적이 있다고 들었는데, 이번 기회에 풀어보게 되었다. 이 문제는 '최대 독립 집합' 개념과 맞닿아 있다.

어떤 그래프 G의 정점들의 집합을 S라고 하자. 이러한 S의 부분 집합 S`을 선택하였을 때, 각 정점들이 인접하지 않는다면 이를 Independent Set(독립 집합) 이라고 부른다. 이 때, 최대로의 정점을 뽑아서 Independent Set을 만드는 것을 Maximum Independent Set이라고 한다.

트리의 각 노드에는 두 가지 경우의 수가 있는데, 하나는 그 노드가 얼리어답터가 되는 경우이고, 다른 하나는 얼리어답터가 안되는 경우이다.
그 노드가 얼리어답터라면, 자식노드는 얼리어답터여도 되고, 아니여도 된다. 반대로 그 노드가 얼리어답터가 아니라면, 자식 노드는 모두 얼리어답터여야 한다.

유사한 문제 - 백준 (트리의 독립집합)

자바 버전 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class baekjoon_2533 {

    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());
        graph = new ArrayList[N+1];
        visited = new boolean[N + 1];
        dp = new int[N + 1][2];
        for (int i = 1; i <= N; i++) {
            dp[i][1] = 1; //자신이 얼리어답터면 1개는 무조건 얼리어답터다
        }
        for (int i = 0; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < N-1; i++) {
            String[] inputs = br.readLine().split(" ");
            int A = Integer.parseInt(inputs[0]);
            int B = Integer.parseInt(inputs[1]);
            graph[A].add(B);
            graph[B].add(A);
        }

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

    private static void dfs(int curNode) {
        visited[curNode] = true;
        for (int child : graph[curNode]) {
            if (!visited[child]) {
                dfs(child);
                
                //현재 노드가 얼리어답터가 아니면 자식은 무조건 얼리어답터
                dp[curNode][0] += dp[child][1];
                //현재 노드가 얼리어답터면 자식 노드는 둘 중 최소
                dp[curNode][1] += Math.min(dp[child][0], dp[child][1]);
            }
        }
    }
}

트리 DP 정석 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static List<Integer>[] childs = new ArrayList[1000001];
    public static int childCount[] = new int[1000001];
    public static int cache[][] = new int[1000001][2];
    static{
        for (int i = 0; i < 1000001; i++) {
            childs[i] = new ArrayList<>();
            for (int j = 0; j < 2; j++) {
                cache[i][j] = -1;
            }
        }
    }
    public static int N;
    public static void main(String[] args){
        Scanner sca = new Scanner(System.in);
        N = sca.nextInt();
        for (int i = 0; i < N-1; i++) {
            int pa = sca.nextInt();
            int ch = sca.nextInt();
            childs[pa].add(ch);
            childs[ch].add(pa);
        }

        dfs(1, -1);
        System.out.println(Math.min(getMinEarly(1, 0, -1), getMinEarly(1, 1, -1)));
        System.out.println();
    }
    public static int dfs(int node, int parent){
        int sum = 1;
        for (int i = 0; i < childs[node].size(); i++) {
            if(childs[node].get(i) == parent)
                continue;
            sum += dfs(childs[node].get(i), node);
        }
        return childCount[node] = sum;
    }
    public static int getMinEarly(int root, int onOff, int parent){
        // 탈출조건
        if(childCount[root] == 1){
            return onOff == 1 ? 1 : 0;
        }
        if(cache[root][onOff] != -1)
            return cache[root][onOff];

        // root가 켜져 있을 때
        if(onOff == 1){
            int sum = 1;
            for (int i = 0; i < childs[root].size(); i++) {
                int child = childs[root].get(i);
                if(child == parent)
                    continue;
                sum += Math.min(getMinEarly(child, 1, root), getMinEarly(child, 0, root));
            }
            return cache[root][onOff] = sum;
        }

        // root가 꺼져 있을 때
        int sum = 0;
        for (int i = 0; i < childs[root].size(); i++) {
            int child = childs[root].get(i);
            if(child == parent)
                continue;
            sum += getMinEarly(child, 1, root);
        }
        return cache[root][onOff] = sum;
    }
}