문제 이해
N개의 마을이 트리로 이루어져있다.
이 때 트리의 방향성은 존재하지 않고, 각 마을마다 주민 수가 주어진다.
몇 개의 마을을 아래와 같은 기준으로 우수 마을로 선정 하려 한다.
-
인접한 두 마을은 모두 '우수 마을'로 선정될 수 없다.
-
'우수 마을'로 선정 되지 못한 마을은 최소 한 개의 '우수 마을'과는 접해 있어야 한다.
이 때 '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 하는 경우를 찾는 문제이다.
문제 풀이
문제 자체는 간단할 수 있다.
먼저 Tree 상황이지만 Root Node가 주어지지는 않았다. 하지만 Node 간 간선에 연결 방향이 존재하지 않으므로 어느 Node가 Root가 되어도 상관없다.
따라서, 나는 임의로 1번 마을을 Root Node로 설정하여 문제를 풀었다.
이후 dfs를 통해 Tree를 순회했다.
마을 T를 우수마을로 선정할 경우를 DP[T][1], 선정하지 않을 경우를 DP[T][0]이라고 생각하자.
DP[T][0] 같은 경우, 자신이 우수 마을이 아니므로 연결된 모든 마을들은 우수 마을일 수도 있고, 우수 마을이 아닐 수도 있다. 따라서 모든 "자식 Node"들에 대하여 해당 자식 Node가 우수 마을인 경우와 우수 마을이 아닌 경우 중 큰 값을 DP[T][0]에 더해주면 된다.
여기서 "자식 Node"들에 대해서만 수행하는 이유는, dfs를 통해 계산을 수행하므로 부모 Node의 계산은 부모 Node가 Main인 DFS 재귀함수에서 계산되어야 하기 때문이다.
DP[T][1]은 자식 Node들이 무조건 우수 마을이 아니여야 하므로 DP[자식 Node][0]값들만 더해주면 된다.
그렇다면 '우수 마을'로 선정되지 못한 마을은 최소 한 개의 '우수 마을'과 접해 있어야 한다는 조건은 어떻게 해결할지 궁금할 것이다.
답을 먼저 말하면 "고려하지 않아도 된다"
우리는 마을 주민 수의 "최댓값"을 구하고 싶다. 즉, 우수 마을을 선정했을 때 우수 마을의 주민 수가 N일 경우, 어떤 경우에도 N을 넘도록 우수 마을을 선정할 수는 없어야 한다.
위 방법을 통해 우리는 마을 주민 수의 "최댓값"을 구할 수 있었다.
만약, 이 "최댓값"의 Case 중 최소 한 개의 '우수 마을'과도 접하지 못한 마을이 있다고 가정하자.
그런데, 최소 한 개의 '우수 마을'과 접하지 못했다는 의미는 해당 마을이 '우수 마을'로 선정되어도 조건에 위반하지 않는다는 것을 의미한다.
마을 주민 수는 항상 양수이므로, 해당 마을을 '우수 마을'로 선정했을 경우 최댓값 N보다 큰 값이 도출될 수 있다. 이는 모순이다.
따라서, 우리가 "최댓값"을 구하기 위한 최선의 선택을 했다면, 당연하게도 우수 마을이 아닌 마을은 최소 한 개의 '우수 마을'과 접해야 한다는 의미를 가진다.
이 문제는 DP도 DP였지만 이 조건을 파악하는게 핵심이였다.
코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N;
static ArrayList<Integer>[] lists;
static int[] cost;
static int[][] DP;
//DP[i][0] : i 마을이 우수마을이 아님
//DP[i][1] : i 마을은 우수마을임
static void dfs(int cur, int prev) {
// cur : 현재 노드
// prev : 부모 노드. 트리의 모든 Node는 최대 1개의 부모 노드를 가지므로
// prev도 1개 값만 가질 것이다.
DP[cur][1] = cost[cur];
// 현재 마을이 우수마을인 상황이므로 주민 수를 더해준다
for(int s:lists[cur]) { // s : 현재 마을의 자식 Node 마을들
if(s==prev) continue;
// 부모 노드의 경우 부모 노드가 Main인(cur 값인) 재귀함수에서
// 처리될 것이다
// 따라서 생략
dfs(s, cur);
DP[cur][0] += Math.max(DP[s][0], DP[s][1]);
// 자식 Node는 우수 마을이여도 되고, 아니여도 된다.
// (현재 Node는 우수마을이 아니므로)
// 따라서 자식 노드가 우수마을인 경우와 아닌 경우 중 큰 값을 더해준다
DP[cur][1] += DP[s][0];
// 현재 마을이 우수마을이므로 자식마을은
// 무조건 우수 마을이 아니여야 한다.
}
}
public static void main(String[] args) throws IOException {
FastReader sc = new FastReader();
N = sc.nextInt();
lists = new ArrayList[N+1];
cost = new int[N+1];
DP = new int[N+1][2];
for(int i =1;i<N+1;i++) lists[i] = new ArrayList<>();
for(int i =1;i<N+1;i++) cost[i] = sc.nextInt();
for(int i=0;i<N-1;i++) {
int tmp1 = sc.nextInt();
int tmp2 = sc.nextInt();
lists[tmp1].add(tmp2);
lists[tmp2].add(tmp1);
}
dfs(1, 0); // 1을 Root Node로 보고 dfs 수행
System.out.println(Math.max(DP[1][1],DP[1][0]));
}
static class FastReader // 빠른 입력을 위한 클래스
}결과
