어떠한 트리의 임의의 노드 정점은(풀이에서는 간편함을 위해 첫 번째 노드라 함)
최대 독립집합에 포함되거나, 안되거나 무조건 두 경우 중 하나
포함을 1, 미포함을 0으로 나타냄
1번째 노드부터 깊이우선탐색(DFS)
dp[i][j] : i번째 노드를 루트노드로하는 서브트리에서, 최대독립집합에 i번째 노드 포함 여부가 j일때 최대 가중치 합
마지막으로
최대 독립집합에 어떠한 노드 A가 포함되면, 인접한 자식 노드는 당연히 포함될 수 없다.
반면, A가 포함되지 않는다면 인접한 자식노드는 포함될 수도, 안 될 수도 있다.
두 가지 경우 중 최대 가중치 합이 더 큰 쪽을 DP에서 확인하여 선택하면 됨.
Code
package test;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class P2213 {
static int[] weight; // weight[i] : i 번재 노드 가중치
static int[] select; // select[i] : 최대 독립집합에서 i번째 노드 포함 여부(포함 : 1, 제외 : 0)
static Integer[][] dp; // dp[i][j] : 포함여부가 j일때, i번째 노드를 루트로 하는 서브트리일 경우 최대 가중치
static ArrayList<ArrayList<Integer>> list = new ArrayList<>(); // 인접 행렬
static ArrayList<ArrayList<Integer>> tree = new ArrayList<>(); // 각 노드의 자식 노드만 저장
static PriorityQueue<Integer> pque = new PriorityQueue<>(); // 최대 독립집합에 포함된 정점
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
// 노드 개수 입력
int N = Integer.parseInt(br.readLine());
weight = new int[N + 1];
select = new int[N + 1];
dp = new Integer[N + 1][2];
for(int i = 0; i <= N; i++) {
list.add(new ArrayList<Integer>());
tree.add(new ArrayList<Integer>());
}
st = new StringTokenizer(br.readLine(), " ");
// 가중치 입력
for(int i = 1; i <= N; i++) {
weight[i] = Integer.parseInt(st.nextToken());
}
// 간선정보(간선 이루는 두 정점) 입력
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());
list.get(a).add(b);
list.get(b).add(a);
}
// tree 생성 (각 노드의 자식 노드 저장, 인접 노드 중 부모노드는 제외)
// 편의를 위해 1을 루트노드로 가정해도 무방
buildTree(1, -1);
/*
최대 독립집합에는 1번째노드가 포함될수도, 안될수도 있음
무조건 위의 두 경우 중 하나
1번째 노드가 포함될 때와 안될 때 최대 가중치 합 비교
더 큰 경우에 따라 최대 독립집합에 1번재 노드 포함 여부 결정
*/
int t1 = dp(1, 0);
int t2 = dp(1, 1);
if (t1 > t2) {
select[1] = 0;
} else {
select[1] = 1;
}
// 최대 가중치 합 출력
sb.append(String.valueOf(Math.max(t1, t2))).append("\n");
findNode(1, select[1]);
/*
for(int i = 0; i <= N; i++) {
for(int j = 0; j < 2; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
*/
// 최대 독립집합에 속하는 정점 출력
while (!pque.isEmpty()) {
sb.append(pque.poll()).append(" ");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
/*
now: 현재 노드
included : 최대 독립집합에 현재 노드 포함 여부
*/
static int dp(int now, int included) {
int result = 0;
if (included == 1) {
// 현재 노드가 포함되면 --> 인접한 자식 노드는 미포함
for (int next : tree.get(now)) {
result += dp(next, 0);
}
// 현재 노드 가중치 추가
result += weight[now];
} else {
// 현재 노드가 미포함
// --> 인접한 자식 노드를 포함할 때, 안 할 때 비교
// 더 큰 가중치 합 쪽을 선택
for (int next : tree.get(now)) {
int t1 = dp(next, 0);
int t2 = dp(next, 1);
if (t1 > t2) {
select[next] = 0;
} else {
select[next] = 1;
}
result += Math.max(t1, t2);
}
}
return dp[now][included] = result;
}
// tree 생성
static void buildTree(int now, int p) {
for (int child : list.get(now)) {
// 각 노드의 자식 노드 저장, 인접 노드 중 부모노드는 제외
if (child != p) {
tree.get(now).add(child);
buildTree(child, now);
}
}
}
/*
최대 독립집합에 포함되는 노드 정점 우선순위 큐에 저장
now: 현재 노드
included : 최대 독립집합에 현재 노드 포함 여부
*/
static void findNode(int now, int included) {
if (included == 0) {
// 현재 노드는 미포함 --> 다음 인접 자식 노드 탐색
for (int next : tree.get(now)) {
findNode(next, select[next]);
}
} else {
// 현재 노드 포함 --> 큐에 저장
// 다음 인접 자식 노드는 무조건 미포함
pque.offer(now);
for (int next : tree.get(now)) {
findNode(next, 0);
}
}
}
}
一期一会