[백준 1949] 우수 마을 / 자바 / dp

#문제

레벨: G4
알고리즘: dp
풀이시간: 30분
힌트 참조 유무: 무

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

---

#문제 풀이

3개의 노드를 부모노드 - 자식노드 관점에서 보면 케이스는 위와 같이 4가지로 나누어집니다. 우린 dp를 자신의 노드가 우수마을인지 아닌지 나눠서 생각해봐야 합니다.
dp[N][2] = 자식 노드 포함해서 현재 노드의 최고의 인원 수

dp[i][0] = 자신이 우수노드가 아닐 때
dp[i][1] = 자신이 우수노드일 때

케이스2를 보면 자식 노드 2와 3은 서로가 우수마을이든지 아니든지 상관이 없습니다.
즉, 옆 자식노드는 상관하지 않아도 된다는 것입니다.

dp[i][1]은 자신이 우수노드인 경우이므로 케이스 1과 같이 자식들이 모두 우수노드가 아닌 경우의 수를 더해줘야합니다.
dp[i][0]은 자신이 우수노드가 아닌 경우으이므로 케이스 2와 같이 자식들이 우수노드이거나, 아닌 경우 모두를 고려해서 더해줘야합니다.

---

#풀이 코드

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

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

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

        // 마을 수 입력
        N = Integer.parseInt(br.readLine());

        // 마을 주민 수 입력
        people = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            people[i] = Integer.parseInt(st.nextToken());
        }

        // 그래프 초기화
        graph = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 트리 연결 정보 입력
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }

        // DP 배열 초기화 
        // [i][0]: i번 마을이 우수마을 아닌 경우
        // [i][1]: i번 마을이 우수마을인 경우
        dp = new int[N+1][2];
        visited = new boolean[N+1];

        // 1번 노드부터 DFS 시작
        dfs(1);

        // 최대 주민 수 출력
        System.out.println(Math.max(dp[1][0], dp[1][1]));
    }

    static void dfs(int node) {
        visited[node] = true;

        // 현재 노드를 우수마을로 선택
        dp[node][1] = people[node];

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

            dfs(child);

            // 현재 노드가 우수마을이면, 자식은 우수마을 아니어야 함
            dp[node][1] += dp[child][0];

            // 현재 노드가 우수마을 아니면, 자식은 우수마을이거나 아니거나 선택 가능
            dp[node][0] += Math.max(dp[child][0], dp[child][1]);
        }
    }
}