[ BOJ ][JAVA][12978] 스크루지 민호 2

www.acmicpc.net/problem/12978

12978번: 스크루지 민호 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	85	31	27	42.188%

문제

구두쇠로 유명한 스크루지 민호가 다스리는 천나라가 있다. 천나라에는 N 개의 도시들이 있는데 각각의 도시들 사이에는 양방향 도로로 이어져 있다. 민호는 도시를 세울 때 최소한의 비용만을 들이고 싶어서 N - 1 개의 도로를 이용해 모든 도시들 사이에는 단 한개의 경로만이 존재하도록 도시를 세웠다.

도시를 건설 한 뒤 이번에는 경찰서를 세우려고 했지만 모든 도시에 경찰서를 걸설하기 아까웠던 민호는 몇몇 도시에 경찰서들을 세우지 않기로 했다. 하지만 경찰이 감시하지 못하는 도시들과 도로들이 생기게 된다면 시민들이 반란을 일으킬 수도 있다고 생각한 민호는 최소한의 도시에 경찰서를 세워 모든 도로들과 도시들을 감시하게 하고 싶어졌다.

한 도시에 경찰서를 세우면 해당 도시와 그 도시에 연결된 양방향 도로들로 연결된 도시들을 감시할 수 있다.

천나라에 있는 도시의 수와 도로들의 연결 상태가 주어질 때 최소 몇개의 도시들에 경찰서를 세워야 모든 도시들과 도로들을 감시할 수 있게 하는지 구해보자.

입력

첫째 줄에는 천나라에 있는 도시의 수 N (2 ≤ N ≤ 100,000) 이 주어진다. 다음 N - 1 줄에 걸쳐 도시들의 연결 상태가 주어진다.

각각의 줄에는 공백을 기준으로 세개의 숫자가 u, v (1 ≤ u, v ≤ N) 가 주어지는데 이는 도시 u와 v가 양방향 도로로 연결이 되어 있다는 것을 의미한다.

출력

첫째 줄에 민호가 경설사를 건설해야 하는 최소 도시의 수를 출력한다.

예제 입력 1

5
4 5
4 2
2 3
1 2

예제 출력 1

2

코드

/*
    TREE + DP 기본
*/
import java.util.*;
import java.io.*;

public class p12978 {
    static int n;
    static List<Integer>[] list;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        list = new ArrayList[n + 1];
        dp = new int[n + 1][2];
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }

        // 사이클을 형성하지 않으므로 아무 노드나 시작점으로 결정해도 상관없다.
        dfs(1, -1);
        // 시작점에서의 메모이제이션 배열을 가져와야한다.
        System.out.println(Math.min(dp[1][0], dp[1][1]));
    }

    static void dfs(int cur, int parent) {
        //dp[cur][0] = 0;
        //dp[cur][1] = 1;

        for (int next : list[cur]) {
            if (next != parent) {
                dfs(next, cur);
                // 현재도시에서 건설하지 않는다면 자식 도시들은 반드시 건설해야한다.
                dp[cur][0] += dp[next][1];
                // 현재도시에서 건설한다면 다음 도시는 건설해도 되고, 안해도 된다.
                dp[cur][1] += Math.min(dp[next][0], dp[next][1]);
            }
        }
        dp[cur][1] += 1;
    }
}