[java] 1949번 우수 마을

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

트리 + dp + dfs 문제이므로 top-down 으로 내려갔다가 올라오면서 dp배열을 업데이트 해주는데,

• dp[n][0] 은 n번 마을이 우수 마을이 아닐 때
• dp[n][1] 은 n번 마을이 우수마을 일 때
  로 나누어 총합을 계산해준다.

🔴 백준 예시를 통한 이해

** dfs를 통해 dfs(현재노드,부모노드) 로 마지막 노드까지 탐방한다.
1. 먼저 시작은 1부터 가겠지용
자식노드가 2 이므로, 아래와 같은 결과

2. 2의 값을 구하기 위해서는 또 dfs(3,2)와 dfs(6,2) 진행

3. dfs(3,2)를 진행합니다.
   다시 한 번 설명하자면, dp[3][0]은 3번 마을이 우수마을이 아닐 때의 경우이므로, 자식노드의 최댓값을 가져오고
   dp[3][1]은 3번 마을이 우수마을일 때의 경우이므로, 자식노드 즉 4번 마을이 우수마을이 아닐 때의 값 = dp[4][0]을 가져와 더해줍니다.

4. dfs(4,3)을 진행
   

5. 5는 자식노드가 없으므로, 드디어! dp값을 구할 수 있습니다.
   

5. 마을 4의 값도 구해줍니다..
   

6. 3번 마을도, 이렇게 우수마을과 인접마을 우수마을로 구성되어집니다
   

7. 이렇게 구해온 값들을 대입하면서, 1의 최댓값을 구하면
   1,3,5,7이 우수마을로 최대 인원은 14000명이 나오는 걸 확인할 수 있습니다.
   

3. 코드

import java.io.*;
import java.util.*;
public class Main {
	static int N;
	static int[] person;
	static int[][] dp;
	static Vector<Integer>[] v;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		String[] input = br.readLine().split(" ");
		
		person = new int[N + 1];
		v = new Vector[N + 1];
		dp = new int[N + 1][2];
		
		for (int i = 0; i <= N; i++) v[i] = new Vector<>();
		for (int i = 1; i <= N; i++) person[i] = Integer.parseInt(input[i - 1]);
		
		for (int i = 0; i < N - 1; i++) { 
			input = br.readLine().split(" ");
			int a = Integer.parseInt(input[0]);
			int b = Integer.parseInt(input[1]);
			v[a].add(b);
			v[b].add(a);
			}

		dfs(1, 0);
		bw.write(Math.max(dp[1][0], dp[1][1]) + "\n");
		bw.flush();

		}

	public static void dfs(int n, int parent) {
	for (int node : v[n]) {
		if (node != parent) {
			dfs(node, n);
			dp[n][0] += Math.max(dp[node][0], dp[node][1]);
			dp[n][1] += dp[node][0];
		}
	}
	dp[n][1] += person[n];
	}
}