[백준] 1949번 우수마을

문제 설명

• https://www.acmicpc.net/problem/1949
• Gold 2
• 풀이 시간 : 40분

문제 풀이

• dfs를 이용한 DP문제이다.
• DP 테이블을 아래와 같이 두고 Top-down 방식의 재귀를 사용한다.

• DP[i][j] : i노드를 j 마을로 지정했을 때 하위 트리에서의 점수 최대값

• dfs에서 아래와 같은 로직으로 진행한다.

1. 현재 노드를 우수마을로 지정했을 때는 다음 노드는 모두 비우수마을로 지정해야함
   -> result = SUM( DP[next][0] )
2. 현재 노드를 비우수마을로 지정했을 떄는 다음 노드는 둘 중 최대값으로 지정해야함
   -> result = SUM ( MAX (DP[next][0], DP[next][1] ) )

소스 코드 (JAVA)

import java.io.*;
import java.util.*;
public class Main {
    static int N;
    static int[] arr;
    static int[][] dp;
    static List<Integer>[] map;

    static int dfs(int cur, int parent, int col) {
        if (dp[cur][col] != -1) return dp[cur][col];

        int result = 0;

        // 현재 노드가 우수 마을이라면 이후 진행 마을은 모두 우수 마을이 아니어야함
        if (col == 1) {
            result = arr[cur];
            for (int next : map[cur]) {
                if (next == parent) continue;
                result += dfs(next, cur, 0);
            }
        }
        // 현재 노드가 우수 마을이 아니라면 이후 진행 마을은 우수 마을이거나 우수 마을이 아니어야함
        else {
            for (int next : map[cur]) {
                if (next == parent) continue;
                result += Math.max(dfs(next, cur, 0), dfs(next, cur, 1));
            }

        }
        return dp[cur][col] = result;
    }
    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        dp = new int[N+1][2];
        map = new ArrayList[N+1];
        for (int i = 1; i <= N; i++)
            map[i] = new ArrayList<>();


        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            Arrays.fill(dp[i], -1);
        }
        for (int i = 0; i < N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a].add(b);
            map[b].add(a);
        }

        int result = Math.max(dfs(1, 0, 0), dfs(1, 0, 1));
        bw.write(result + "\n");

        bw.flush();
    }

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

/**
 * 우수마을 (19:15)
 *
 * - N : 마을 개수 (N <= 10000)
 * - 양방향 이동 가능한 트리구조
 * 1. 우수 마을끼리는 인접할 수 없다.
 * 2. 우수 마을이 아닌 마을은 적어도 우수 마을과 이어져 있어야함
 * 3. 우수 마을 주민 수의 총합을 최대로 해야한다.
 *
 * N
 * n1 n2 ....nN
 *
 */