문제
N개의 마을이 트리 구조로 연결되어 있다. 각 마을을 "우수 마을"로 선정하면 그 인구 수만큼 점수를 얻는다. 단, 인접한 두 마을이 동시에 우수 마을이 될 수 없다. 또한 우수 마을로 선정되지 않은 마을은 반드시 우수 마을과 인접해야 한다. 이 조건을 만족하면서 우수 마을의 인구 합을 최대화하는 문제이다.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에 N개 마을의 인구 수가 주어진다. 이후 N-1개의 줄에 인접한 두 마을 번호가 주어진다.
출력
우수 마을의 인구 합의 최댓값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 1000 3000 4000 1000 2000 2000 3000 1 2 2 3 4 2 4 5 6 2 6 7 | 9000 |
풀이
트리 DP 기법을 사용한다. 각 노드에 대해 "선택" 또는 "미선택" 두 가지 상태를 유지하며 DFS로 리프 노드부터 루트 방향으로 최적값을 합산한다.
dp[v][0]: v 노드를 미선택할 때 v 서브트리의 최대 인구 합dp[v][1]: v 노드를 선택할 때 v 서브트리의 최대 인구 합- 루트 1번부터 DFS를 수행한다. 각 자식 노드
siv에 대해 재귀 호출 후 DP 값을 계산한다. - v를 선택하면 인접 자식은 모두 미선택이어야 한다:
dp[v][1] += dp[siv][0] - v를 미선택하면 자식은 선택하거나 미선택 중 큰 값을 취한다:
dp[v][0] += max(dp[siv][0], dp[siv][1]) - 최종 답은
max(dp[1][0], dp[1][1])이다.
핵심 아이디어: 트리의 특성상 부모-자식 관계가 명확하므로 DFS 탐색 중 자식 노드의 DP 값이 먼저 확정된다. "인접한 두 마을 동시 선택 불가" 조건은 부모-자식 관계로만 제한되므로, 자식이 선택됐으면 부모는 반드시 미선택이어야 하는 점화식으로 표현된다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Day59BOJ1949우수마을DFS로DP사용 { // 1949 우수마을 선택 DFS로 DP 사용하는 기본적인 문제
static int N;
static int[] P;
static List<Integer>[] list;
static int[][] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
P = new int[N + 1];
list = new ArrayList[N + 1];
dp = new int[N + 1][2];
st = new StringTokenizer(br.readLine());
for (int n = 1; n < N + 1; n++) {
P[n] = Integer.parseInt(st.nextToken());
} // 0번 미사용
for (int n = 0; n < N + 1; n++) {
list[n] = new ArrayList<>();
} // 0번 생성은 해도 연결된 노드 없어서 신경안써도 됨.
for (int n = 0; n < N - 1; n++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
list[n1].add(n2);
list[n2].add(n1);
}
dfs(1, 0);
System.out.println(Math.max(dp[1][0], dp[1][1]));
br.close(); // 최종적으로 처음 시작된 1번에서 선택하냐 마냐에 값이 중첩됨.
}
private static void dfs(int curr, int root) {
for (int siv : list[curr]) {
if (siv != root) { // 상단 노드로 회기하지 않도록
dfs(siv, curr); // 현재를 상단으로 보는 하위 노드까지 내려감.
dp[curr][1] += dp[siv][0];
dp[curr][0] += Math.max(dp[siv][0], dp[siv][1]);
} // 현재를 선택했으면, 인접한 siv는 미선택,
} // 현재를 선택하지 않았으면, siv를 선택하냐, 마냐 중 큰 값
dp[curr][1] += P[curr];
} // 모든 노드 자신의 값을 선택한 칸에 기록, 리프노드부터 시작되는 부분
}복잡도
- 시간: O(N) — 트리의 각 노드와 간선을 한 번씩 방문
- 공간: O(N) — DP 배열 및 인접 리스트