백준, boj) 2213. 트리의 독립집합 ( C / C++ )

1. 문제 링크

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

2213번: 트리의 독립집합

2. 문제 개요

가중치가 가장 큰 최대 독립 집합을 찾는 것.

 

3. 문제 힌트

DP를 사용하자. 나를 포함하거나 포함하지 않거나를 기준으로.

경로 역추적을 하기 위해서 포함했을 때, 체크를 해줄 수 있도록 bool 배열을 하나 만든다.

 

4. 문제 풀이

주어진 가중치값과 경로를 인접 리스트에 넣어준다.

그리고 편의상 DFS탐색을 위한 리스트도 만들어 주었다. ( 1 -> 2 -> 1 -> 2... 와 같은 것 방지)

 

시작점(1)으로 부터 시작점을 포함한 경우, 포함하지 않은 경우 중 큰 값을 선택해야 한다.

dp(int cur, bool include) 함수를 정의하는데, cur 즉, 현재 점을 include 포함하느냐 안 하느냐 이다.

int v1 = dp(1, false)

int v2 = dp(1, true)를 비교해야 한다.

재귀적으로 들어가서 가장 마지막 노드까지 가야 한다. 그래서 값을 쌓아 올린다는(?) 느낌으로..

 

나를 포함하는 경우는 나와 인접한 노드는 무조건 포함하지 않아야 한다.

for (모든 인접한 노드에 대하여)

 ans += dp(인접한 노드, false)와 같이 호출해야 한다.

 

나를 포함하지 않는 경우는 나와 인접한 노드는 포함해도 되고 포함하지 않아도 된다.

for(모든 인접한 노드에 대하여)

  int v1 = dp(인접 노드, false)

  int v2 = dp(인접 노드, true)

  if(포함한 것이 포함하지 않은 것보다 크다면)

      포함 여부 배열[인접 노드] = true

else

      포함 여부 배열[인접 노드]=false

가 될 것이다.

 

 

그리고 역추적이 남았다.

역추적은 그냥 포함 여부 배열의 true인 부분을 차례대로 출력하면 될 것 같으나, 한참 포함되었다가 도중에 포함되지 않는 경우가 있을 수 있다. 따라서 시작했던 점을 기준으로 재귀적으로 들어가서 배열을 만들어야 한다.

 

tracert(int cur, bool include) 함수를 만들어서, 

tracert(1, check [1])시작점을 기점으로 추적해야 한다.

 

cur점일 때 check [cur] == true라면, 포함한다는 뜻이고,

정답 배열에 삽입한다. 그리고 그것과 인접한 노드들은 모두 포함하지 않아야만 한다.

 

현재 노드가 포함되지 않을 경우에는 check배열에 저장했던 것을 따르도록 한다.

 

5. 코드

 

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

vector<vector<int>> adj;
vector<vector<int>> order;
vector<int>weight;
vector<int> answer;
int dptable[10001][2];
//안한것, 한것.
bool check[10001];

void tracert(int cur, bool include)
{
	if (include) {
		answer.push_back(cur);
		for (int i = 0; i < order[cur].size(); i++) {
			int next = order[cur][i];
			tracert(next, 0);
		}
	}
	else {
		for (int i = 0; i < order[cur].size(); i++) {
			int next = order[cur][i];
			tracert(next, check[next]);
		}
	}

}
 
int dp(int cur, bool include)
{
	int &cache = dptable[cur][include];
	if (cache != -1)	return cache;

	if (include)
	{
		int ans = 0;
		for (int i = 0; i < order[cur].size(); ++i){
			int next = order[cur][i];
			ans += dp(next, 0);
		}
		return cache = ans + weight[cur];
	}
	else
	{
		int ans = 0;
		for (int i = 0; i < order[cur].size(); ++i) {
			int next = order[cur][i];
			int t1 = dp(next, 0);
			int t2 = dp(next, 1);
			if (t1 < t2)
				check[next] = true;
			else
				check[next] = false;
			ans += (max(t1, t2));
		}
		return cache = ans;
	}
}

void dfs(int cur, int pre)
{
	int len = adj[cur].size();

	for(int i = 0; i < len; ++i)
	{
		int next = adj[cur][i];
		if (next == pre)
			continue;
		order[cur].push_back(next);
		dfs(next, cur);
	}
	return;
}


int main()
{
	int n;
	scanf("%d", &n);
	adj.resize(n + 1);
	weight.resize(n + 1);
	order.resize(n + 1);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &weight[i]);
		dptable[i][0] = dptable[i][1] = -1;
	}
	for (int i = 1; i < n; ++i) {
		int from, to;
		scanf("%d %d", &from, &to);
		adj[from].push_back(to);
		adj[to].push_back(from);
	}
	
	dfs(1, 0);
	
	int t1 = dp(1, 1);
	int t2 = dp(1, 0);

	if (t1 > t2)
		check[1] = true;
	else
		check[1] = false;
	printf("%d\n", max(t1, t2));

	tracert(1, check[1]);
	sort(answer.begin(), answer.end());

	for (int i = 0; i < answer.size(); ++i)
		printf("%d ", answer[i]);

	return 0;
}

 

 

지적, 댓글 언제나 환영입니다~