(백준) 트리의 독립집합 _ 2213

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

 

🐢 설명

일반적인 트리DP + 경로 추적 문제이다. 기본적으로 트리dp 문제는 2차원 dp를 이용해서 해당 정점을 사용하느냐 마느냐에 따라서 해당 노드의 가중치를 더하거나 말거나 하는 방식으로 진행된다. 이 문제에서는 서로 인접하지 않는 정점들을 골라서 최대의 가중치를 구하고 해당 정점들의 번호를 순서대로 나열해야 한다.

 

문제에서 말하는 독립 집합은 결국 각 정점들을 인접하지 않게 뽑았을 때 최대로 값을 가지는 정점들의 부분집합인데 이때

 

특정 정점이 독립집합이라면 (YES)

• 인접 정점은 독립집합일 수 없다. (NO)

특정 정점이 독립집합이 아니라면 (NO)

• 인접 정점은 독립집합일 수 있다. (YES)
• 인접 정점은 독립집합이 아닐 수 있다. (NO)

이런 가짓수가 존재한다. 이 형태를 기억하면서 문제를 보자.

 

일단 가중치를 계산하기 위해서 사용하는 2차원 DP는 [YES ? NO][정점 번호] 와 같은 형태를 갖게된다. YES는 해당 정점이 독립집합에 포함되는 경우를, NO는 포함되지 않는 경우를 의미한다. 이후 dfs를 통해 특정 노드를 잡아서 완전탐색을 하면 된다. 이때 그래프에서 따로 방향에 대해서는 조건을 주지 않았으므로 양방향으로 해줘야 하며 따라서 방문체크를 해줘야 한다.

 

dfs를 통해 리프노드까지 내려간 후 해당 노드에서부터 YES인 경우와 NO인 경우마다 각각 가중치를 더해주면 된다. 이때 경로 탐색을 위해 추가적으로 필요한 부분이 있는데 2차원 trace[][] 리스트이다.

 

trace 이차원 리스트는 각 정점들이 각 경우에 따라 지나왔던 정점들을 담는 변수이다. 이때 리프노드들은 초기값으로 독립정점 경우에 맞춰서 기본값을 넣어주면 된다.

// 독립 정점이라면 가중치를 더해준다. 해당 정점을 이력에 추가한다.
dp[YES][root] += w[root];
trace[YES][root].add(root);

// 독립 정점이 아니라면 가중치는 없다. 이력도 없다.
dp[NO][root] = 0;

 

이후 DFS를 돌면서 현재 정점의 독립/비독립 여부에 따라 인접노드에서 지나왔던 노드들의 이력을 가져와서 추가해주면 된다.

/* dfs 내부에서 현재 정점이 독립이냐, 비독립이냐에 따라 나뉜다. */

[독립 정점]
// 독립 정점은 인접 정점은 비독립 정점
dp[YES][root] += dp[NO][child];
// 독립 정점이라면 비독립 정점의 이력을 가져옴
trace[YES][root].addAll(trace[NO][child]);

[비독립 정점]
// 비독립 정점은 인접 정점은 독립 정점, 비독립 정점 둘중 더 큰값을 갖는다.
dp[NO][root] += Math.max(dp[YES][child], dp[NO][child]);
// 비독립 정점이라면 더 큰 인접 정점의 이력을 가져온다.
if (dp[YES][child] > dp[NO][child]) {
    trace[NO][root].addAll(trace[YES][child]);
} else {
    trace[NO][root].addAll(trace[NO][child]);
}

이후 모든 정점들을 방문하고 난 후 시작 정점에서 독립인 경우, 아닌 경우를 확인해서 더 큰값과 해당 경우의 이력을 정렬해서 뽑아준다.

 

🐢코드

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static ArrayList<Integer>[] adj;
	static ArrayList<Integer>[][] trace;
	static int[] w;
	static boolean[] visited;
	static int[][] dp;
	static int YES = 0;
	static int NO = 1;

	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st;

		N = Integer.parseInt(br.readLine());

		w = new int[N + 1];
		adj = new ArrayList[N + 1];
		visited = new boolean[N + 1];
		dp = new int[2][N + 1];
		trace = new ArrayList[2][N + 1];
		for (int i = 0; i < N + 1; i++) {
			adj[i] = new ArrayList<>();
			trace[0][i] = new ArrayList<>();
			trace[1][i] = new ArrayList<>();
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			w[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			adj[u].add(v);
			adj[v].add(u);
		}

		dfs(1);

		StringBuilder answer = new StringBuilder();
		if (dp[YES][1] > dp[NO][1]) {
			answer.append(dp[YES][1]).append("\n");
			trace[YES][1].sort(null);
			for (Integer traceNode : trace[YES][1]) {
				answer.append(traceNode).append(" ");
			}
		} else {
			answer.append(dp[NO][1]).append("\n");
			trace[NO][1].sort(null);
			for (Integer traceNode : trace[NO][1]) {
				answer.append(traceNode).append(" ");
			}
		}

		System.out.print(answer);
	}

	private static void dfs(int root) {
		visited[root] = true;

		dp[YES][root] += w[root];
		trace[YES][root].add(root);

		dp[NO][root] = 0;

		for (Integer child : adj[root]) {
			if (visited[child]) continue;
			dfs(child);

			dp[YES][root] += dp[NO][child];
			trace[YES][root].addAll(trace[NO][child]);

			dp[NO][root] += Math.max(dp[YES][child], dp[NO][child]);
			if (dp[YES][child] > dp[NO][child]) {
				trace[NO][root].addAll(trace[YES][child]);
			} else {
				trace[NO][root].addAll(trace[NO][child]);
			}
		}
	}
}

🐢 마무리