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

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

2213번: 트리의 독립집합

 

먼저 이 문제를 dp문제라고 생각하자. 

 

요즘 dp스터디라서 dp인걸 알고 풀고 있음. 

 

문제 이해부터 하자면 트리가 있을때, 인접한 정점은 고르지 못한다. 이 조건을 만족하면서 고른 정점들의 가중치 합이 최대가 되는 값과 그 고른 정점들을 구하려는 문제이다. 

 

결론부터 얘기하면 subtree로 나눈다. 

subtree들이 모여서 그 위의 부모트리의 값을 결정한다. 

 

부모노드에서 자식들의 값으로만 부모노드의 결과값을 결정할 수 있는가가 문제가 된다.

 

이건 아이디어의 문제인것 같은데, 어떤 정점이 포함될때, 포함되지 않을때의 값으로 나누어서 생각한다. 

 

그렇게 되면 부모노드가 포함될때는 

자식노드들은 모두 포함할 수 없다. 

 

dp[parent][1] = 모든 자식노드의 dp[child][0] 값들의 합이다. 

 

여기서 의문이 생길 수 있다. dp[child][0]이 어떻게 이루어졌는지 먼저 살펴보지 않았기 때문에 과연 이래도 되는가 생각할 수 있는데 그러면 부모노드를 포함하지 않을때에 대해서 생각해보자 

 

dp[parent][0] = max(모든 자식노드의 dp[child][1], dp[child][0] 의 합) 

 

이렇게 구성되기 때문에 하위 노드에서 올라올때는 문제를 풀기위해서 필요한 조건들이 모두 빠짐없이 빽빽하게 계산되면서 상위노드로 올라온다. 

 

포함되는 정점들은 어떻게 구할까 

 

vector를 따로 설정해서 dp값을 정할때, 자식노드가 포함하는 모든 정점들을 넣고 후에 자기 자신을 넣으면 된다. 

 

오름차순 출력은 우선순위 큐를 이용해서 출력하였다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 10101

vector<int> child[MAX];
vector<int> answer[MAX][2];
int n, a, b, root, cnt=1, INF = 987654321;
int weight[MAX];
int check_ord[MAX];
int dp[MAX][2];
bool start;

void make_tree(int x, int y) {
	if (!start) {
		root = x;
		child[x].push_back(y);
		check_ord[x] = cnt++;
		check_ord[y] = cnt++;
		start = true;
	}
	else {
		if (check_ord[x] > check_ord[y]) {
			if (check_ord[x] == INF)
				check_ord[x] = cnt++;
			child[y].push_back(x);
		}
		else if (check_ord[x] < check_ord[y]) {
			if (check_ord[y] == INF)
				check_ord[y] = cnt++;
			child[x].push_back(y);
		}
		else {
			child[x].push_back(y);
			check_ord[x] = cnt++;
			check_ord[y] = cnt++;
		}
	}
}

void solve(int ch) {
	for (int i = 0; i < child[ch].size(); i++) {
		solve(child[ch][i]);
	}
	int tmp1 = 0, tmp2 = 0, chid;
	for (int i = 0; i < child[ch].size(); i++) {
		chid = child[ch][i];
		tmp1 += dp[chid][0];
		for (int j = 0; j < answer[chid][0].size(); j++) {
			answer[ch][1].push_back(answer[chid][0][j]);
		}
		if (dp[chid][0] < dp[chid][1]) {
			tmp2 += dp[chid][1];
			for (int j = 0; j < answer[chid][1].size(); j++) {
				answer[ch][0].push_back(answer[chid][1][j]);
			}
		}
		else {
			tmp2 += dp[chid][0];
			for (int j = 0; j < answer[chid][0].size(); j++) {
				answer[ch][0].push_back(answer[chid][0][j]);
			}
		}
	}
	answer[ch][1].push_back(ch);
	dp[ch][1] = tmp1 + weight[ch];
	dp[ch][0] = tmp2;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> weight[i];
	}
	for (int i = 1; i <= n; i++) {
		check_ord[i] = INF;
	}
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b;
		make_tree(a, b);
	}
	solve(root);
	priority_queue<int> pq;

	if (dp[root][0] < dp[root][1]) {
		cout << dp[root][1] << "\n";
		for (int i = 0; i < answer[root][1].size(); i++) {
			int temp = answer[root][1][i];
			pq.push(-temp);
		}
		while (!pq.empty()) {
			cout << -pq.top() << " ";
			pq.pop();
		}
	}
	else {
		cout << dp[root][0] << "\n";
		for (int i = 0; i < answer[root][0].size(); i++) {
			pq.push(-answer[root][0][i]);
		}
		while (!pq.empty()) {
			cout << -pq.top() << " ";
			pq.pop();
		}

	}
}