[백준/BOJ] 백준 2213번 : 트리의 독립집합

www.acmicpc.net/problem/2213

2213번: 트리의 독립집합

트리에서 다이나믹 프로그래밍(트리DP?)를 이용해 문제를 해결했다. 해당 노드를 독립 집합에 포함하는지, 포함하지 않는지에 따라 해당 노드를 루트로 하는 트리의 최대 독립 집합의 크기를 구하는 방식으로 트리의 최대 독립 집합의 크기를 구한다. 최대 독립 집합에 속하는 정점을 구하는 방법은, 이전 노드가 최대 독립 집합에 선택되었는지를 판단하여 이전 노드가 최대 독립 집합에 선택되지 않았다면 지금 노드를 선택하는 것과 선택하지 않는 것 중 더 큰 값을 만들 수 있는 쪽을 선택하고 이전 노드가 최대 독립 집합에 선택되었다면 지금 노드는 선택하지 않는 방법을 이용하여 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> w(10001);
vector<int> adj[10001];
vector<int> maked(10001, 0);
int cache[10001][2];

struct node
{
	int number;
	int weight;
	vector<node*> children;
};

void Pre()
{
	for (int i = 0; i < 10001; i++)
		for (int j = 0; j < 2; j++)
			cache[i][j] = -1;
}

//root번을 루트로하는 트리를 만든다
node* treeMake(int root)
{
	node* ret = new node();

	ret->number = root;
	ret->weight = w[root];

	maked[root] = 1; //해당 정점은 트리로 만들어졌다고 표시

	for (int i = 0; i < adj[root].size(); i++)
	{
		if (maked[adj[root][i]] == 1)
			continue;

		ret->children.push_back(treeMake(adj[root][i]));
	}

	return ret;
}

//here노드가 독립집합에 포함하는지, 포함하지 않는지에 따라 (포함할때(check:1)와 포함하지 않을때(check:0)) here노드를 루트로 하는 트리의 최대 독립집합의 크기를 구한다  
int Solve(node* here, int check)
{
	int& ret = cache[here->number][check];

	if (ret != -1)
		return ret;

	//자식노드가 없을때
	if (here->children.size() == 0)
	{
		if (check == 1)
		{
			ret = here->weight;
			return ret;
		}

		else
		{
			ret = 0;
			return ret;
		}
	}

	if (check == 1)
		ret = here->weight;
	else
		ret = 0;

	for (int i = 0; i < (here->children).size(); i++)
	{
		//현재 노드가 독립집합에 포함될때 다음노드는 독립집합에 포함되지 않는다
		if (check == 1)
		{
			ret += Solve(here->children[i], 0);
		}

		//현재 노드가 독립집합에 포함되지 않는다면 다음노드는 독립집합에 포함될수도 있고 포함되지 않을 수 도 있다
		else
			ret += max(Solve(here->children[i], 1), Solve(here->children[i], 0));
	}

	return ret;
}

void nodeFind(node* here, int before_selected, vector<int>& selected)
{
	int here_selected;

	if (before_selected == 0) //이전노드가 최대 독립집합에 선택되지 않았을때
	{
		//지금 노드를 선택하는게 더 큰 독립집합을 만들 수 있을때
		if (cache[here->number][0] < cache[here->number][1])
		{
			selected.push_back(here->number);
			here_selected = 1;
		}

		else
		{
			here_selected = 0;
		}
	}

	//이전노드가 최대 독립집합에 선택되었다면 지금 노드는 무조건 선택할 수 없다
	else //before_selected == 1
	{
		here_selected = 0;
	}

	for (int i = 0; i < (here->children).size(); i++)
	{
		nodeFind(here->children[i], here_selected, selected);
	}
}

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

	int input;
	int u, v;
	node* tree;

	Pre();

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> input;
		w[i] = input;
	}

	for (int i = 0; i < n - 1; i++)
	{
		cin >> u >> v;

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

	tree = treeMake(1); //1번 정점을 루트로한 트리를 만든다

	//루트노드를 독립집합에 포함할때와, 포함하지 않을때 중 큰 값을 출력한다
	cout << max(Solve(tree, 1), Solve(tree, 0)) << "\n";

	vector<int> selected;
	nodeFind(tree, 0, selected);

	sort(selected.begin(), selected.end());

	for (int i = 0; i < selected.size(); i++)
	{
		cout << selected[i] << " ";
	}

	return 0;
}