[백준] 1949 - 우수 마을 (Java)

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

 

지금까지 푼 트리 DP 문제와 같은 방법으로 풀면 된다.

다만 3번 조건이 애매하게 마음 속에 걸렸다.

뭔가 직감적으로는 내 풀이가 3번 조건을 자연스럽게 만족하는 정답을 도출할 것 같은데 확실하진 않은 느낌..

 

우선 풀이는 다음과 같다.

현재 노드를 루트로 하는 서브트리에 대해 현재 노드가 우수마을인 경우, 최적해와 우수마을이 아닌 경우 최적해를 저장하는 DP 테이블을 짜고 다음과 같이 점화식을 세운다.

 

dp[node][우수마을o] = sum( dp[child][우수마을x], ... )

dp[node][우수마을x] = sum( max(dp[child][우수마을o], dp[child][우수마을x]), ... )

 

부모 노드가 우수마을이 아닌 경우, 모든 자식에 대해 우수마을 선정 여부는 상관이 없으므로 둘 중에 최적해를 취하도록 했다.

이때 마음에 걸린 것은 혹시 부모가 우수마을이 아닐 때, 자식들도 모두 우수마을이 아닌 경우가 최적이면 어떡하지? 하는 생각이 들었다.

물론 이 경우엔 부모가 우수마을이 되는 것이 더 최적이긴 하지만, 만약 그 부모의 부모가 우수마을이라서 부모가 우수마을이 되지 않아도 된다면? 이런 생각이 들어서 긴가민가하면서 일단 구현하고 냈는데 맞았다. (prove by AC..)

 

결론적으로는 자식들이 모두 우수마을이 아닌 경우가 최적이라면 부모가 우수마을이 되는 것이 최적이라서 문제가 없다고 한다.

만약 부모의 부모가 우수마을인 경우가 최적이라서 부모가 우수마을이 아니어야 하고, 그때 자식들이 마침 모두 우수마을이 아닌 것이 최적이라면

 

그림과 같은 예시를 생각해볼 수 있다.

위 그림에서는 1억 3개를 골라서 3억을 만드는 것이 최적이다.

따라서 루트의 자식 노드가 우수마을이 아니고, 그 자식들이 모두 우수마을이 아니더라도 루트의 자식노드에 대해 계산할 때 자식들이 모두 우수마을이 아니더라도 해집합에 일단 포함시켜야 한다고 이해했다.

 

 

그 위에 최적해를 유도하는 노드가 존재하면 이때는 기존에 포함하지 않았던 1번 노드를 포함하도록 하면 된다.

 

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 Main {

    private static List<List<Integer>> graph = new ArrayList<>();
    private static int[] vertex_list;
    private static boolean[] visited;
    private static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        visited = new boolean[n];
        dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
            visited[i] = false;
        }
        vertex_list = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        for (int i = 0; i < n-1; i++) {
            String[] line = br.readLine().split(" ");
            int start = Integer.parseInt(line[0]) - 1;
            int end = Integer.parseInt(line[1]) - 1;
            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        visited[0] = true;
        int ans1 = solve(0, true);
        visited[0] = true;
        int ans2 = solve(0, false);


//        for(int i = 0; i < n; i++) {
//            System.out.println(Arrays.toString(dp[i]));
//        }

        System.out.println(Math.max(ans1, ans2));
    }

    private static int solve(int node, boolean isUsu) {
        int uSuValue = isUsu ? 1 : 0;

        if (dp[node][uSuValue] != 0)
            return dp[node][uSuValue];

        int ret = 0;
        if (isUsu) {
            ret += vertex_list[node];
            for (int next_node : graph.get(node)) {
                if (!visited[next_node]) {
                    visited[next_node] = true;
                    ret += solve(next_node, false);
                }
            }
        } else {
            for (int next_node : graph.get(node)) {
                if (!visited[next_node]) {
                    visited[next_node] = true;
                    int v1 = solve(next_node, true);
                    visited[next_node] = true;
                    int v2 = solve(next_node, false);
                    ret += Math.max(v1, v2);
                }
            }
        }
        dp[node][uSuValue] = ret;
        visited[node] = false;
        return ret;
    }
}

 

그리고 파이썬을 벗어나니 파이썬이 얼마나 편했는지도 다시 깨닫는다..

입력받을 때마다 파이썬이 너무 그리워진다 ㅋㅋ