[백준 1949] 우수 마을

문제 링크 : 1949번: 우수 마을 (acmicpc.net)

1949번: 우수 마을

 

트리에서의 다이나믹 프로그래밍 문제이다.

 

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

 

위 조건을 만족하도록 하는 선정된 모든 '우수 마을' 의 인구수의 총 합이 최댓값이 되도록 만들어야 하는 문제이다.

다이나믹 프로그래밍 문제이므로 base case 와 optimal substructure 을 구하여 해결해보도록 하자.

그 전에 트리에서 degree 가 1인 정점 x 를 임의로 선정한 후에 Base case 를 고려해보도록 한다.

 

우선, 함수 dfs 와 배열 dp 에 대한 설명은 다음과 같다.

 

void dfs(int cur, int before)
=> 현재 마을(cur)에서 다음 마을(next)로 이동한다.
그리고 다음 마을에서 만들어진 모든 '우수 마을' 의 인구수 합의 최댓값을 이용하여,
현재 마을(cur) 의 모든 '우수 마을'의 인구수 합을 최댓값으로 갱신해주도록 한다.

int dp[cur] 
=> cur 위치에서 선정된 모든 '우수 마을' 의 인구수 합의 최댓값 

 

① base case 

정점 x 에 대하여 dfs 를 통해 가장 하단부에 도착했다고 가정하자.

 

 

가장 하단부에 도착할 경우, 다음 마을에 대한 정보가 없으므로 dp[cur] = "cur 마을의 인구수" 로 갱신하고 return 해준다.

이러한 처리에 대한 코드는 다음과 같다.

 

void dfs(int cur, int before) 
{
	if (v[cur].size() == 1 && before != 0) {
		dp[cur] = people[cur];
		return;
	}
    
    ...
}

 

② optimal substructure

case 1 : 현재 마을 2 에 속한 인구수가 다음 마을 3, 4, 5 에 속한 인구수의 총 합보다 작은 경우

 

 

case 2 : 현재 마을 6 에 속한 인구수가 다음 마을 7, 8, 9 에 속한 인구수의 총 합보다 큰 경우

 

 

이에 대한 optimal substructure 을 구하면 다음과 같다.

 

\(dp[x] = max(people[x], \sum_{i = 1}^{n}dp[x \to next_i])\)

 

그러나 위와 같이 구하게 된다면 정답이 아니다.

좀 더 확장된 case 를 고려해봐야 한다.

 

case 3 : 현재 마을 1에 속한 인구수와 2번 마을의 다음 마을들에 대해 선정된 '우수 마을' 의 인구수 합의 최댓값과

6번 마을의 다음 마을들에 대해 선정된 '우수 마을' 의 인구수 합의 최댓값을 전부 더한 값이

1번 마을의 다음 마을인 2번 마을과 6번 마을에 대해 선정된 '우수 마을' 의 인구수 합의 최댓값을 더한 값보다 큰 경우

 

 

case 4 : 현재 마을 1에 속한 인구수와 2번 마을의 다음 마을들에 대해 선정된 '우수 마을' 의 인구수 합의 최댓값과

6번 마을의 다음 마을들에 대해 선정된 '우수 마을' 의 인구수 합의 최댓값을 전부 더한 값이

1번 마을의 다음 마을인 2번 마을과 6번 마을에 대해 선정된 '우수 마을' 의 인구수 합의 최댓값을 더한 값보다 작은 경우

 

 

 

이에 대한 optimal substructure 을 구하면 다음과 같다.

 

\(dp[x] = max(people[x] + \sum_{i=1}^{n}\sum_{j=1}^{m}dp[x \to next_i\to next_j], \sum_{i = 1}^{n}dp[x \to next_i])\)

 

사실 위 식을 어거지로 표현해보긴 했는데(...?) 대략적으로 위와 같이 표현이 가능하다.

이전에 만들었던 식에서 people[x] 에다가 다음 마을의 다음 마을들에 대한 모든 정보를 다 더해주는 것이 핵심이다.

 

위 식에 대해 코드로 나타내면 다음과 같다.

void dfs(int cur, int before) 
{
	...
    
	int next_value = 0, next_next_value = people[cur];
	for (int next : v[cur]) {
		if (next == before)
			continue;
		dfs(next, cur);
		next_value += dp[next];
		for (int next_next : v[next]) {
			if (next_next == cur)
				continue;
			next_next_value += dp[next_next];
		}
	}
	dp[cur] = max(next_value, next_next_value);
}

 

전체 코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int people[10001], dp[10001];
vector<int> v[10001];

void input() 
{
	int from, to;

	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> people[i];
	for (int i = 1; i <= N - 1; i++) {
		cin >> from >> to;
		v[from].push_back(to);
		v[to].push_back(from);
	}
}

void dfs(int cur, int before) 
{
	if (v[cur].size() == 1 && before != 0) {
		dp[cur] = people[cur];
		return;
	}

	int next_value = 0, next_next_value = people[cur];
	for (int next : v[cur]) {
		if (next == before)
			continue;
		dfs(next, cur);
		next_value += dp[next];
		for (int next_next : v[next]) {
			if (next_next == cur)
				continue;
			next_next_value += dp[next_next];
		}
	}
	dp[cur] = max(next_value, next_next_value);
}

void solution() 
{
	int x = 0;

	for (int i = 1; i <= N; i++) {
		if (v[i].size() == 1)
			x = i;
	}
	dfs(x, 0);
	cout << dp[x];
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	input();
	solution();

	return 0;
}