[트리에서의 동적 계획법 단계] 백준 2231번 트리와 독립집합

문제

그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 에지가 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로 정의한다. 독립 집합이 공집합일 때 그 크기는 0이라고 하자. 크기가 최대인 독립 집합을 최대 독립 집합이라고 한다.

문제는 일반적인 그래프가 아니라 트리(연결되어 있고 사이클이 없는 그래프)와 각 정점의 가중치가 양의 정수로 주어져 있을 때, 최대 독립 집합을 구하는 것이다.

입력

첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 가중치이다(1 ≤ i ≤ n). 셋째 줄부터 마지막 줄까지는 에지 리스트가 주어지는데, 한 줄에 하나의 에지를 나타낸다. 에지는 정점의 쌍으로 주어진다. 입력되는 정수들 사이에는 콤마가 없고 대신 빈칸이 하나 혹은 그 이상 있다. 가중치들의 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 최대 독립집합의 크기를 출력한다. 둘째 줄에는 최대 독립집합에 속하는 정점을 오름차순으로 출력한다. 최대 독립 집합이 하나 이상일 경우에는 하나만 출력하면 된다.

 

1 . 어느 정점에서 시작해도 상관없음 해당 정점이 포함되는가 포함되지 않는가로 구분되기 때문

2. 포함된다면 => 연결된 정점은 포함되지 않아야 함.

  포함되지 않는다면 => 연결 정점이 포함되는 경우와 포함되지 않는 경우중 최대 값

3. 이동 시에는 연결된 간선으로 밖에 못가므로 중복이 발생하는 경우는 이전 정점이 다음 정점이 되는 경우다

따로 visit처리 할 필요없이 prev와 next가 다르면 됨.

 

4. tracking은 포함되는 경우에 ans에 추가해 주고, 포함 되지 않는 경우는 다음정점이 포함될 때와 포함되지 않을 떄 중 

더 큰 가중치인 부분으로 이동.

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

vector<int> edge[10001];
vector<int> ans;
int cost[10001];
int dp[10001][2]; //1 => 해당 정점 포함 , 0 = > 미포함
int N;

int solution(int prev, int cur, int state)
{
	if (dp[cur][state] != -1)
	{
		return dp[cur][state];
	}

	if (state)
		dp[cur][state] = cost[cur];
	else
		dp[cur][state] = 0;

	for (int i = 0; i < edge[cur].size(); i++)
	{
		int next = edge[cur][i];
		//이미 방문시에 이동 x 2->1 1->2 ,,,,2->1 방지
		if (prev == next)
			continue;
		if (state)
			dp[cur][state] += solution(cur, next, 0); // 근접으로는 안가야함.
		else
			dp[cur][state] += max(solution(cur, next, 0), solution(cur, next, 1)); //가거나 안간 값중 최대
	}
	return dp[cur][state];
	
}
void tracking(int prev, int cur, bool state)
{
	if (state)
	{
		ans.push_back(cur);
		for (int i = 0; i < edge[cur].size(); i++)
		{
			int next = edge[cur][i];
			if (prev == next)
				continue;
			tracking(cur, next, 0);
		}
	}
	else
	{
		for (int i = 0; i < edge[cur].size(); i++)
		{
			int next = edge[cur][i];
			if (prev == next)
				continue;
			if (dp[next][1] >= dp[next][0])
				tracking(cur, next, 1);
			else
				tracking(cur, next, 0);
		}
	}
}

int main() {
	
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> cost[i];
		dp[i][0] = -1;
		dp[i][1] = -1;
	}
	for (int i = 1; i <= N - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	int temp1 = solution(-1, 1, 1);
	int temp2 = solution(-1, 1, 0);

	if (temp1 > temp2)
	{
		tracking(-1, 1, 1);
	}
	else
	{
		tracking(-1, 1, 0);
	}
	cout << max(temp1, temp2) << endl;
	sort(ans.begin(), ans.end());
	for (auto i : ans)
		cout << i << " ";
}