[BOJ][C/C++] 1949번 : 우수 마을

🔗링크

1. 문제 풀이

---

예전에 풀었던 얼리어답터 문제와 유사한 트리DP 문제

조건

1. 임의의 정점이 우수 마을이라면 인접한 모든 정점은 우수 마을 X
2. 우수 마을이 아닌 정점은 적어도 하나의 우수 마을과 인접해야 함
3. 트리 구조이기에 Cycle이 존재하지 않음
4. 주민 수의 총 합이 최대가 되게 구해야 함

여기서 우리는 다이나믹 프로그래밍 기법을 활용할 수 있다.

어떠한 정점에 대한 정보를 저장하기 위한 배열을 만든다.

---

만약 정점이 하나라면 정점에 대한 정보는 다음과 같다.

이제 작은 문제로 부터 점화식을 유도한다.

Ex) 정점 (1, 2) 각 정점 주민 수는 (10, 20)

1을 루트로 둔다면

---

즉 다음과 같은 식을 만들수 있다.

이제 깊이 우선 탐색을 통해 DP[루트][0] 과 DP[루트][1]의 값을 구할 수 있다!

---

그림으로 설명

리프 노드까지 DFS을 진행

2. 코드

#include<stdio.h>
#include<vector>
#define MAX(a,b)(a>b?a:b)
using namespace std;

int tree[10001],dp[10001][2],V[10001], N;
vector<int>Edge[10001];

void f(int v) {
	if (V[v])return;
	dp[v][0] += tree[v];
	V[v] = 1;
	int max = 0;
	for (int i = 0; i < Edge[v].size(); i++)
		if (!V[Edge[v][i]]) {
			f(Edge[v][i]);
			dp[v][0] += dp[Edge[v][i]][1];
			dp[v][1] += MAX(dp[Edge[v][i]][0], dp[Edge[v][i]][1]);
		}
}
int main() {
	int u, v;
	scanf("%d",&N);
	for (int i = 1; i <= N; i++)
		scanf("%d",&tree[i]);
	for (int i = 0; i < N - 1; i++) {
		scanf("%d %d",&u,&v);
		Edge[u].push_back(v);
		Edge[v].push_back(u);
	}
	f(1);
	printf("%d",MAX(dp[1][0],dp[1][1]));
	return 0;
}

3. 후기

배고파