백준 2213 트리의 독립집합

www.acmicpc.net/problem/2213

 

 

독립집합: 서로 간선으로 연결되어 있지 않은 정점들의 집합

 

체크 표시한 정점들의 집합은 독립집합이다

각 정점에는 가중치가 있어서 가중치의 합이 최대가 되는 트리의 독립집합을 구하는 문제

 

문제에 핵심은, 어떤 정점이 독립집합에 포함되어 있다면 그 자식은 포함되지 않아야 한다

예를 들어 위에서 2가 독립집합이라면 바로 아래 자식 2, 7은 포함되면 안 된다

2가 독립집합이 아니라면 2, 6은 독립집합에 포함되어도 되고, 안 되어도 된다

 

트리의 독립집합은 DP로 풀 수 있다

D[v][0] : 정점 v가 독립집합에 포함되지 않은 경우 최댓값

D[v][1] : 정점 v가 독립집합에 포함된 경우에 최댓값

 

이 두 경우를 구하면 v를 루트로 하는 서브 트리의 독립집합을 구할 수 있다

 

D[v][0] 인 경우

정점 v가 독립집합에 포함되지 않은 경우의 최댓값

정점 v가 독립집합에 포함되지 않았으므로 자식은 독립집합에 포함이 될 수도, 안 될 수도 있다

각 자식들의 포함되었을 경우, 안 되었을 경우의 최댓값을 합치면 D[v][0]의 값이 된다

 

$w_i = v$의 자식일 때,

$D[v][0]=\sum max(D[w_i][0], D[w_i][1])$

 

D[v][1] 인 경우

정점 v가 독립집합에 포함되었을 경우, 자식은 독립집합에 포함되면 안 된다

문제에서 주어진 가중치를 A[v]라고 하면

 

$D[v][1]=\sum D[w_i][0] + A[v]$

 

여기까지 코드로 구현하면 다음과 같다

void dpdfs(int now, int parent) {
	for (int i = 0; i < v[now].size(); i++) {
		if (v[now][i] == parent) continue;
		else dpdfs(v[now][i], now); //모든 경우에 대해 재귀를 보낸다
	}

	d[now][0] = 0;
	d[now][1] = w[now]; //1은 포함하는 경우이므로 가중치 더한다
	for (int i = 0; i < v[now].size(); i++) { //모든 자식들에 대해
		if (v[now][i] == parent) continue;
		
		d[now][0] += max(d[v[now][i]][0], d[v[now][i]][1]); //max(d[w_i][0], d[w_i][1])
		d[now][1] += d[v[now][i]][0]; //d[w_i][0] + w[now]
	}
}

 

그런데 이 문제는 최대 독립집합의 크기 뿐만 아니라 독립집합에 속하는 정점도 구해야 한다

dp를 도는 도중에 체크하는 방법도 있을 것 같은데 여기서는 다 구한 뒤에 되돌아가면서 찾는 방법으로 구현했다

 

void trace(int now, int isinclude, int parent) {
	if (isinclude == 1) { //포함인 경우
		res.push_back(now); //독립집합임
		for (int i = 0; i < v[now].size(); i++) {
			if (v[now][i] == parent) continue;
			trace(v[now][i], 0, now); //부모가 포함이면 자식들은 무조건 안 포함으로
		}	
	}
	else { //포함 아니면
		for (int i = 0; i < v[now].size(); i++) { //모든 자식들에 대해
			if (v[now][i] == parent) continue;

			if (d[v[now][i]][0] < d[v[now][i]][1]) {
				trace(v[now][i], 1, now); //자식도 포함이면
			}
			else trace(v[now][i], 0, now); //포함 아니면
		}
	}
}

돌아갈 때도 똑같이 해당 정점이 포함일 경우와 안 포함인 경우를 나눠서 들어간다

정점이 포함이면 독립집합이므로 정답 벡터에 추가하고 자식들에 대해 안 포함으로 재귀를 돌린다

정점이 안 포함이면 자식이 포함인지 안 포함인지를 확인해서 각 경우에 맞게 재귀를 돌린다

 

마지막 정점까지 다 계산 후에 나온 정답 벡터를 오름차순 정렬하면 답

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, w[10001], d[10001][2];
vector<int> v[10001], res;

void dpdfs(int now, int parent) {
	for (int i = 0; i < v[now].size(); i++) {
		if (v[now][i] == parent) continue;
		else dpdfs(v[now][i], now); //모든 경우에 대해 재귀를 보낸다
	}

	d[now][0] = 0;
	d[now][1] = w[now]; //1은 포함하는 경우이므로 가중치 더한다
	for (int i = 0; i < v[now].size(); i++) { //모든 자식들에 대해
		if (v[now][i] == parent) continue;
		
		d[now][0] += max(d[v[now][i]][0], d[v[now][i]][1]); //max(d[w_i][0], d[w_i][1])
		d[now][1] += d[v[now][i]][0]; //d[w_i][0] + w[now]
	}
}

void trace(int now, int isinclude, int parent) {
	if (isinclude == 1) { //포함인 경우
		res.push_back(now); //독립집합임
		for (int i = 0; i < v[now].size(); i++) {
			if (v[now][i] == parent) continue;
			trace(v[now][i], 0, now); //부모가 포함이면 자식들은 무조건 안 포함으로
		}	
	}
	else { //포함 아니면
		for (int i = 0; i < v[now].size(); i++) { //모든 자식들에 대해
			if (v[now][i] == parent) continue;

			if (d[v[now][i]][0] < d[v[now][i]][1]) {
				trace(v[now][i], 1, now); //자식도 포함이면
			}
			else trace(v[now][i], 0, now); //포함 아니면
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	for (int i = 0, a, b; i < n - 1; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dpdfs(1, 0);
	cout << max(d[1][0], d[1][1]) << '\n';

	if (d[1][0] < d[1][1]) {
		trace(1, 1, 0); //포함이면
	}
	else {
		trace(1, 0, 0); //포함 아니면
	}

	sort(res.begin(), res.end());
	for (int i = 0; i < (int)res.size(); i++) {
		cout << res[i]<< " ";
	}
	return 0;
}