공부 기록

문제 조건

'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

이 문제의 경우는 우수 마을에 포함할지 말지 모두 구한 후 조건에 맞는지 확인하는 방식으로 푼다면 O(2^N)으로 시간초과가 날 것이다.

'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다. => DP를 사용하면 될 것 같다.

우수마을의 경우 트리 형태이고, 이 트리에서 DP를 사용해서 문제를 풀어야 한다.

이 문제에선, 부모 노드를 우수 마을에 포함할 경우, 자식노드는 우수 마을에 포함하면 안된다.

그리고 일반 마을이 부모 노드일 경우, 자식 노드에는 우수 마을이 있어야 한다.(합을 최대로 구해야 하니까)

dp[i][0]: i번 마을이 우수 마을이 아니었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값
dp[i][1]: i번 마을이 우수 마을이었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값

아무 노드나 루트로 삼고 DFS를 진행한다. => 1로 시작하자

왜냐면 조건중에

나라는 트리(Tree) 구조로 이루어져 있으며, 즉 마을과 마을 사이를 직접 잇는 N-1개의 방향 없는 길이 있으며,

모든 마을은 연결되어 있다. 는 조건이 있기 때문이다.

이 문제에서 주어진 문제는 방향이 없는 연결을 가지는 트리이며, 모든 노드가 루트 노드가 될 수 있다.

DFS를 사용한 이유는 순회를 하면서 우수마을 조건에 포함하고 포함하지 않는 식의 백트래킹을 이용하기 위해서이다.

리프노드에 도달하게 되면,

노드 5와 같이 다시 거슬러 올라오면서 dp값을 채우도록 한다.

노드 2까지 올라오면 다른 분기점으로 내려가면서

마찬가지로 방문하지 않은 노드까지 찾아내려간다.

결론적으로 업데이트된 dp의 최종 결과는 아래와 같다.

그리고 이를 적용한 코드는 아래와 같다

import java.util.*;

public class Main {
	public static int max = 0;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int people[] = new int[n + 1];
		LinkedList<Integer> connections[] = new LinkedList[n + 1];

		for (int i = 1; i <= n; i++) {
			people[i] = in.nextInt();
			connections[i] = new LinkedList<Integer>();
		}

		for (int i = 1; i < n; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			connections[a].add(b);
			connections[b].add(a);
		}

		/*
		 * dp[i][0]: i번 마을이 우수 마을이 아니었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값,
		 * 
		 * dp[i][1]: i번 마을이 우수 마을이었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값
		 * 
		 */
		int dp[][] = new int[n + 1][2];
		boolean isVisited[] = new boolean[n + 1];
		int start = 1;
		dfs(start, isVisited, people, dp, connections);

		System.out.println(Math.max(dp[start][0], dp[start][1]));
	}

	public static void dfs(int root, boolean[] isVisited, int[] people, int[][] dp, LinkedList<Integer> connections[]) {
		isVisited[root] = true;
		for (int next : connections[root]) {
			if (!isVisited[next]) {
				dfs(next, isVisited, people, dp, connections);
			}
		}
		dp[root][0] = 0;
		dp[root][1] = people[root];
		for (int next : connections[root]) {
			dp[root][0] += Math.max(dp[next][0], dp[next][1]);
			dp[root][1] += dp[next][0];
		}
	}
}

주의할 점은 top down방식으로 dp를 업데이트 하게 되면 분기점 등에서 겹치는 값이 생길 수 있으므로

botton up 방식으로 값을 업데이트 하도록 해야 한다.