[1949] 우수 마을

🔗 문제 링크

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

🔍 문제 설명

N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다.

이 나라의 주민들에게 성취감을 높여 주기 위해, 다음 세 가지 조건을 만족하면서 N개의 마을 중 몇 개의 마을을 '우수 마을'로 선정하려고 한다.

• '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.

• 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.

• 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

각 마을 주민 수와 마을 사이의 길에 대한 정보가 주어졌을 때, 주어진 조건을 만족하도록 '우수 마을'을 선정하는 프로그램을 작성하시오.

⚠️ 제한사항

• $(1 ≤ N ≤ 10,000)$

• 주민 수는 10,000 이하이다.

---

🗝 풀이 (언어 : Java)

이 문제도 DFS와 DP를 동시에 이용해서 풀이한 문제이다. 루트 노드를 기준으로 루트를 고르면 자식 노드를 고르면 안되고, 자식 노드를 고르면 부모 노드를 고르면 안되는 두가지 경우를 나눠서 구해야하는 문제이다. 그래서 결과값을 누적해서 이용할 배열을 2차원으로 선언했다. 현재 루트노드의 0번째 인덱스에는 해당 루트 노드를 안고른 경우, 1번째 인덱스는 해당 루트 노드를 고른 경우이다. 안고른 경우는 자식 루트 노드의 포함 여부와 관계없이 최대값을 고른다. 여기서 헷갈렸던 점은 부모가 포함이 안되었으면 자식은 무조건 포함되어야 한다고 생각했는데, 자식중 하나만 우수마을이면 되므로 부모와 자식 둘 다 우수마을이 아닌 케이스도 존재한다.

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 {
    private static int[][] dp; // DP 배열
    private static int[] people; // 마을별 사람수

    private static void dfs(int x, int prev, List<Integer>[] arr) {
        dp[x][0] = 0; // 첫 시작점 수 안고른 경우
        dp[x][1] = people[x]; // 고른 경우
        for(Integer next : arr[x]) {
            if(next.intValue() == prev) // 연결된 정점 중에 부모는 스킵
                continue;
            dfs(next, x, arr); // 자식 정점으로 탐색
            // 현재 부모 노드를 안고른 경우, 자식 서브 트리의 루트 노드 포함 여부 관계없이 최대값을 현재 노드 값없이 더하기
            dp[x][0] += Math.max(dp[next][0], dp[next][1]);
            // 현재 부모 노드를 고른 경우, 자식 서브 트리의 루트 노드를 포함하지 않는 경우의 최대값을 현재 노드의 값과 더하기
            dp[x][1] += dp[next][0];
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int 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());
        List<Integer>[] arr = new ArrayList[n+1]; // 양방향 그래프 생성
        for(int i = 1; i <= n; i++)
            arr[i] = new ArrayList<>();
        dp = new int[n+1][2];
        for (int i = 1; i < n; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st2.nextToken()), b = Integer.parseInt(st2.nextToken());
            arr[a].add(b); // 양방향이므로 둘다 반대쪽 노드 넣기
            arr[b].add(a);
        }
        br.close();
        dfs(1, -1, arr); // DFS 탐색으로 DP 배열 완성
        System.out.print(Math.max(dp[1][0], dp[1][1])); // 시작 루트 노드가 우수 마을인 경우, 아닌 경우 중 최대값
    }
}