boj, 백준) 1949. 우수 마을 ( C / C++)

1. 문제 링크

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

1949번: 우수 마을

2. 문제 개요

N개의 마을로 이루어진 나라가 있다. 1부터 N까지 번호가 붙어있다고 하자. 이 나라는 Tree구조로 이루어져 있다.

마을과 마을 사이를 잇는 N-1개의 길이 있으며 양방향 간선이다.

 

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

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

(3) 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

 

우수마을을 선정하는 프로그램을 작성해보자.

 

3. 문제 힌트

   tree로 나타내어야 한다.

dp[cur][state]로 두고, cur은 마을 번호, state는 cur마을을 우수마을로 선택하면 1, 선택하지 않으면 0을 나타내도록 하자.

 

현재 마을을 우수 마을로 선택한다고 가정하자.

그럼 다음 마을은 규칙(2)에 의해서 무조건 우수 마을이 아니어야 한다.

 

현재 마을을 우수 마을이 아니라고 해보자.

다음마을은 우수마을이 아닐 수도 있고, 우수마을일 수도 있다.

그런데 여기서 주목해야 할 점은 규칙(3) 번이다.

 

우수 x -> 우수x -> 우수x 이렇게 계속 선택될 것 같아 보이지만, 문제의 특성상, 최댓값을 항상 갖고 나가기 때문에 규칙(3) 번은 자연스레 만족된다. 물론 위의 예처럼 우수마을이 연달아서 안될 수도 있다. 하지만 최댓값에 만족되지 않기 때문에 max() 함수에서 자연스레 탈락되며 항상 규칙(3) 번을 만족한다.

 

4. 문제 풀기

메모이제이션을 하면서 dp를 구현해야 한다.

그리고 Tree이기 때문에 어느 노드를 잡아서 시작해도 그 노드는 root가 되며,

내가 잡은 root가 우수마을인지, 우수마을이 아닌지 2개를 구한 다음 두 개의 최댓값이 정답이 된다.

 

dp의 점화식은 3번 힌트란에서 다 설명했다.

 

그리고 특별한 점은 주어진 맵은 양방향이다. 입력받을 때도 양방향으로 받았다. 그리고 edge가 더 많았다면, DFS를 사용해서 경로를 결정지어주어야 한다.

하지만 이문제는 Tree이고 cycle이 없다.

따라서 dp함수에서 그냥 이전 노드를 함께 매개변수로 넣어서 무한 반복되지 않도록 했다.

 

 

5. 코드

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

int n,dp_table[10001][2];//cur, state
vector<int> v;
vector<vector<int>> adj;

//n-1개의 edge니까 cycle이 없다.dfs트리 안해줘도 됨.
int dp(int cur, int pre, int state)
{
	//memoization
	int &cache = dp_table[cur][state];
	if (cache != -1)	return cache;
	int ans = 0;
	int len = adj[cur].size();

	if (state == 0) {
		for (int i = 0; i < len; ++i) {
			int next = adj[cur][i];
			if (next == pre)	continue;
			int ret1 = dp(next, cur, 0);
			int ret2 = dp(next, cur, 1);
			ans += max(ret1, ret2);
		}
		return cache = ans;
	}
	else{
		for (int i = 0; i < len; ++i) {
			int next = adj[cur][i];
			if (next == pre)	continue;
			ans += dp(next, cur, 0);
		}
		return cache = ans + v[cur];
	}
}
int main()
{
	scanf("%d", &n);
	v.resize(n + 1);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &v[i]);
	memset(dp_table, -1, sizeof(dp_table));
	adj.resize(n + 1);
	for (int i = 0; i < n - 1; ++i) {
		int from, to;
		scanf("%d %d", &from, &to);
		adj[from].push_back(to);
		adj[to].push_back(from);
	}

	printf("%d", max(dp(1,0,0),dp(1,0,1)));

	return 0;
}

6. 결과 사진

 

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