[백준] 1949번 우수 마을

문제 위치 : https://www.acmicpc.net/problem/1949

---

 

1. Approach

 

(1) 트리를 이용한 다이나믹 프로그래밍으로 접근한다.

 

- 모든 마을 간 연결을 한 후에 문제에 나와 있듯이 Tree 구조로 만든다.

- 현재 마을이 우수 마을로 선정되었다면 이어져있는 다음 마을들은 우수 마을이 되면 안된다.

- 현재 마을이 우수 마을로 선정되지 않았다면 이어져있는 다음 마을들은 우수 마을이 되거나, 아니어도 된다.

- 경우의 수는 다음 마을이 우수 마을이 되지 않는 경우 1가지

- 현재 마을이 우수 마을이 아닐 경우에는 다음 마을이 우수 마을이 되는 경우 2가지가 있다.

 

(2) DP 배열 정의

 

-> DP[idx][2] : idx 마을이 선정되거나 안되었을 경우 (0 or 1) 까지의 우수 마을 주민의 최대 총합

 

(3) 후기

 

1. 트리를 이용한 문제들은 많이 사용되기 때문에, 확실히 이해하고 넘어가자.

2. 다이나믹 프로그래밍 문제들을 풀면서 느낀 것은 여러 종류의 자료구조와 알고리즘을 모두 접할 수 있고, 거기서 최선을 찾아내는 능력을 키우는 것 같다.

2. Source Code

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAX 10000
using namespace std;
/*
	문제 설명

	1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.

    2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 
	   '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.

    3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 
	   적어도 하나의 '우수 마을'과는 인접해 있어야 한다.
*/
int n;
int country[MAX + 1];
vector<int> tree[MAX + 1];
vector<int> villages[MAX + 1];
int dp[MAX + 1][2];
bool check[MAX + 1];

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

	result = 0;

	for (int i = 0; i < tree[cur].size(); i++)
	{
		int next_country = tree[cur][i];
		int first, second;
		// 현재 도시가 우수마을로 선정되든, 안되든 다음 마을은 우수마을이 아닐 수가 있다.
		first = solution(next_country, 0);
		second = -1;
		// 현재 도시가 우수마을로 선정이 안된다면안되든 다음 마을은 우수마을이 아닐 수가 있다.
		if (!state)
		{
			second = solution(next_country, 1);
		}

		result += max(first, second);
	}

	if (state)
	{
		result += country[cur];
	}
	return result;
}

void MakeTree(int idx)
{
	for (int i = 0; i < villages[idx].size(); i++)
	{
		int nextidx = villages[idx][i];

		if (!check[nextidx])
		{
			tree[idx].push_back(nextidx);
			check[nextidx] = true;
			
			MakeTree(nextidx);
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> country[i];
	
	int s, e;
	for (int i = 0; i < n - 1; i++)
	{
		cin >> s >> e;
		villages[s].push_back(e);
		villages[e].push_back(s);
	}

	// 트리 만들기
	check[1] = true;
	MakeTree(1);


	memset(dp, -1, sizeof(dp));
	cout << max(solution(1, 1), solution(1, 0));

	return 0;
}