[백준 1949] 우수 마을 - JAVA

BOJ Link

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

 

 

풀이 과정

트리에서의 다이나믹 프로그래밍(+dfs) 문제다.

 

우선 임의의 정점을 루트로 잡고, top-down dfs로 리프 노드로 이동한다.

 

이후, 부모의 dp배열

dp[parent][1]  - 우수 마을일 때

dp[parent][0]  - 우수마을이 아닐 때

 

를 bottom-up으로 다음과 같이 채워나간다.

 

한 노드가 우수 마을 이라면, 인접한 노드는 모두 우수 마을이 아니여야 한다. 따라서,

dp[parent][1] += dp[child][0]; 를 자식의 개수만큼 반복한다.

 

한 노드가 우수 마을이 아니라면, 인접한 노드는 우수 마을일 수도, 아닐 수도 있다. 따라서,

dp[parent][0] += Math.max(dp[child][0], dp[child][1]); 를 자식의 개수만큼 반복한다.

 

유의할 점

1. 이진 트리가 아니며, 1-999-3과 같은 연결이 이뤄질 수도 있다. (일반적인 트리를 구성하고 시작하면 안된다.)

2. 우수 마을의 순서쌍이 oxox 뿐만 아니라 oxxo의 꼴도 나올 수 있다.

3. 간선이 N-1개인 희소그래프이므로 인접 리스트 구현이 유리하다.

4. 트리의 특성상 루트를 제외한 모든 노드의 부모는 1개이며,

bottom-up으로 접근한다면, 인접한 노드 중 부모 노드 1개를 제외한 모든 노드는 자식 노드이다.

5. bottom-up bfs로 접근한다면, 리프 노드의 level이 다를 수 있어 복잡해진다.

(부모 dp를 구할 때 갱신이 안된 자식들로 이뤄질 수 있다.)

 

제출 코드

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

class Main {
    static int N, dp[][];
    static List<Integer>[] adj;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int ROOT = 1;

        int[] cost = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
        }

        adj = new List[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            adj[from].add(to);
            adj[to].add(from);
        }

        dp = new int[N + 1][2];
        for (int i = 1; i <= N; i++) {
            dp[i][1] = cost[i];
        }

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

    static void dfs(int node, int parent) {

        for (int i = 0; i < adj[node].size(); i++) {
            int adjNode = adj[node].get(i);

            if (adjNode != parent) {
                dfs(adjNode, node);
                dp[node][0] += Math.max(dp[adjNode][0], dp[adjNode][1]);
                dp[node][1] += dp[adjNode][0];
            }
        }
    }

}