백준 1949번 우수 마을 (JAVA)

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

1949번: 우수 마을

 

트리에서 루트가 정해져 있지 않다는 점을 이용한 DP 문제이다.

가장 처음에 이런 유형의 문제를 풀 때 루트가 정해진 트리로 접근했다가 틀렸던 기억이 있다. 비슷한 문제로 사회망 서비스 SNS 문제가 있다.

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

2533번: 사회망 서비스(SNS)

 

DP 문제를 풀때는 결국 문제를 작게 쪼개려고 노력해야 한다고 생각한다.

이 문제의 경우에는 루트 노드로 정한 마을이 우수 마을로 선택되는가 / 선택되지 않는 가의 두가지 경우에 따라서 답이 달라지고, 그것을 DP의 형태로 풀어서 문제를 해결하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.function.Function;

public class Main {

    static int[][] dp;
    static int[] popul;
    static int N;
    static ArrayList<Integer>[] roads;
    static Function<String, Integer> stoi = Integer::parseInt;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = stoi.apply(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        popul = new int[N + 1];
        dp = new int[N + 1][2]; // 0 -> 1번 노드 선택 O 1 -> 1번 노드 선택 X
        roads = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            popul[i] = stoi.apply(st.nextToken());
            roads[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int s = stoi.apply(st.nextToken());
            int e = stoi.apply(st.nextToken());
            roads[s].add(e);
            roads[e].add(s);
        }
        dfs(1, 0);
        System.out.println(Math.max(dp[1][0], dp[1][1]));

    }

    private static void dfs(int now, int parent) {
        for (int road : roads[now]) {
            if (road != parent) {
                dfs(road, now);
                dp[now][0] += Math.max(dp[road][0], dp[road][1]);
                dp[now][1] += dp[road][0];
            }
        }
        dp[now][1] += popul[now];
    }


}

 

특정 노드를 루트 노드로 정하면 우리가 아는 트리의 형태로 트리를 재배열할 수가 있다.

이후 부모 노드로 거슬러올라가지않으며(road != parent)

dfs를 반복하면 된다.

dp[now][0]인 경우는 현재 마을이 우수마을이 아닌 경우이며, 이 경우에는 내 자식이 우수마을인 경우도, 아닌 경우도 있을 수 있다.

dp[now][1]인 경우는 현재 마을이 우수마을인 경우이며, 이 경우에 내 자식 마을은 모두 우수마을이 아니어야만 한다.