백준 / 2213 트리의 독립 집합 C++

www.acmicpc.net/problem/2213

2213번: 트리의 독립집합

이전에 푼 우수 마을 문제와 유사한 문제이다. 

i 번 노드가 독립집합의 원소가 아니면, i번 노드의 자식 노드는 독립집합의 원소가 되든 안 되든 상관 없고,

i번 노드가 독립집합의 원소라면, 자식 노드는 독립집합의 원소가 될 수 없다.

 

i번 노드가 독립집합의 원소이고 루트로 하는 서브트리에서의 가능한 최댓값을 dp[i][1], 독립집합이 아닐 때를 dp[i][0]로 잡으면 dp[i][0] += max(dp[next][1], dp[next][0]), dp[i][1] += dp[next][0] 를 반복하면 된다.

 

또한 이 문제에서는 독립집합을 이루는 원소들을 구해야 하는데 처음에는 set 컨테이너를 이용하여 독립집합의 원소가 될 때, 연결 노드를 체크하고, 연결 노드가 set에 존재하면 제거, 그리고 해당 노드를 삽입하는 과정을 하려했다.

 

하지만, 구현해보니 어디선가 케이스를 빼먹었는지 하나 씩 빠져서 출력이 되길래 그냥 dfs를 한 번 더 돌려서 독립집합을 만들었다. 독립집합은 root 노드부터 시작하여, dp[node][1] > dp[node][0]를 만족하고, 직전에 탐색한 노드가 독립집합의 원소가 아니어야 독립집합의 원소이다. 이를 자식 노드에 대해 반복시킨다.

 

코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>

using namespace std;

int n;
int weight[10001];
vector<int>tree[10001];
bool check[10001];
int dp[10001][2];
vector<int>result; // 경로
bool check2[10001]; // 경로에서 이전 노드 연결 여부 확인

// 현재 노드가 독립집합 원소면 다음 노드는 무조건 안됨
// 현재 노드가 독립집합 원소 아니면 다음 노드는 상관 없음
// dp[i][0] : i가 독립집합 아닐 때, i를 루트로 하는 서브트리에서의 최댓값
// dp[i][1] : i가 독립집합 일 때, "
// dp[i][0] += max(dp[next][0], dp[next][1])
// dp[i][1] += dp[next][0]

void make_tree()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> weight[i];

		check[i] = false;
		check2[i] = false;

		dp[i][0] = 0;
		dp[i][1] = 0;
	}
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
}

void search(int node)
{
	check[node] = true;
	dp[node][0] = 0;
	dp[node][1] = weight[node];

	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i];
		if (check[next] == false) {
			search(next);
			dp[node][0] += max(dp[next][0], dp[next][1]);
			dp[node][1] += dp[next][0];
		}
	}
}

// dp[node][1] > dp[node][0] 이면서 연결된 노드가 경로에 포함 안 되어있음
// 인수 : 현재 노드, 이전 노드
void path(int node, int prev)
{
	if (dp[node][1] > dp[node][0]) {
		if (check2[prev] == false) {
			result.push_back(node);
			check2[node] = true;
		}
	}

	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i];
		if (next != prev)
			path(next, node);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	make_tree();
	search(1); // 루트 1로 잡음
	path(1, 1); // 루트 1의 부모 노드는 자기 자신으로 처리
	sort(result.begin(), result.end());

	cout << max(dp[1][0], dp[1][1]) << '\n';
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << ' ';
}