[C++]백준 - 2213번 문제

2213번: 트리의 독립집합 (acmicpc.net)

2213번: 트리의 독립집합

 

2213번 : 트리의 독립집합

---

그래프 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을 넘지 않는 자연수이다.

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

DP와 트리 문제입니다.

 

트리이기 때문에 사이클은 포함되지 않습니다.

 

저는 이 트리에서 어떤 노드를 최대 독립 집합에 포함할 것인지 결정할 것입니다.

 

우선 한 점을 루트라고 가정하고, 루트를 포함했을 때, 그리고 포함하지 않았을 때의 경우의 수를 알아봅니다.

 

1. 루트를 포함했다면, 루트와 간선이 연결된 노드들은 포함될 수 없습니다.

 

2. 포함하지 않았다면, 루트와 간선이 연결된 노드들을 포함하거나 포함하지 않을 수 있습니다.

 

우리는 DP를 통해서 두가지 경우를 모두 볼 것입니다.

 

DP[i][j] = i 번째 노드가 j의 경우에 최대값

 

* j = 0일 경우, 노드를 최대집합에 포함하지 않음/ 1일 경우 포함함

 

예를 들어)

 

DP[0][1]을 구할 경우, 0과 연결된 간선이 1, 2가 있다고 가정합시다.

 

0번째 노드가 포함되었으니 1과 2는 포함될 수 없습니다.

 

DP[0][1] = DP[1][0] + DP[2][0]일 것입니다.

 

반면 DP[0][0]을 구할 경우,

 

1번째 노드와 2번째 노드는 포함될수도, 포함되지 않을 수도 있습니다.

 

DP[0][0] = MAX(DP[1][0], DP[1][1]) + MAX(DP[2][0], DP[2][1]) 일 것입니다.

 

모든 과정이 끝나면, 루트를 포함했을 때와 포함하지 않았을 때 두 경우를 비교해 큰 쪽을 출력하면 정답입니다.

 

코드

---

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

int* node;
int** dp;
bool* visited;
vector<int>* graph;
vector<int> answer_set;

//DFS 알고리즘
void solve(int current)
{
	dp[current][1] += node[current];
	for (int next : graph[current])
	{
		if (visited[next]) continue;
		visited[next] = true;
		solve(next);
		dp[current][0] += max(dp[next][0], dp[next][1]);
		dp[current][1] += dp[next][0];
	}
}

//역추적
//prev = (bool)이전 노드가 포함되었는가?
void find_set(int current, bool prev)
{
	bool checked = false;
    
    //이전 노드가 포함되지 않았으며, 현재 노드를 포함한게 더 큰 값이면 추가
	if (!prev && dp[current][1] > dp[current][0])
	{
		answer_set.push_back(current + 1);
		checked = true;
	}
    //DFS
	for (int next : graph[current])
	{
		if (visited[next]) continue;
		visited[next] = true;
		find_set(next, checked);
	}
}

int main()
{
	int N;
	scanf("%d", &N);
	
    //동적 할당
	node = new int[N];
	visited = new bool[N];
	dp = new int*[N];
	graph = new vector<int>[N];
    
    //입력부
	for (int i = 0; i < N; i++)
	{
		visited[i] = false;
		dp[i] = new int[2];
		dp[i][0] = 0;
		dp[i][1] = 0;
		scanf("%d", &node[i]);
	}

	int a, b;
	while (scanf("%d", &a) != EOF)
	{
		scanf("%d", &b);
		a--; b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
    
	visited[0] = true;
	solve(0);
	
	printf("%d\n", max(dp[0][0], dp[0][1]));
	fill_n(visited, N, false);
	visited[0] = true;

	find_set(0, 0);
	sort(answer_set.begin(), answer_set.end());
	for (int answer : answer_set) printf("%d ", answer);


	for (int i = 0; i < N; i++) delete[] dp[i];
	delete[] node;
	delete[] dp;
	delete[] visited;
	delete[] graph;
	return 0;
}

 

그 외

---