BOJ [1949] 우수 마을

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

 

 

1. 분류

Tree
Dynamic Programming

 

 

 

2. 풀이

 

Tree DP라고 불리는 유형의 문제이다.

문제의 3가지 조건에 맞춰 DP 배열을 업데이트 해주자.

 

풀이 전략은 다음과 같다.

 - DP 테이블 정의

 - DFS로 노드 탐색

 - 부모 노드 방문 중 자식 노드에서 얻을 수 있는 최고의 점수를 업데이트

 

1. DFS로 각 노드를 계속 타고 내려간다.

  1) 각 노드에 방문할 때마다 일반 마을/우수 마을의 기본값을 설정한다.

    - dp[isGood][idx]로 정의한다.

    - isGood = 0이면 일반, 1이면 우수마을이다.

    - 일반 마을이면 값은 0, 우수 마을의 경우 해당 마을의 인구 수로 초기화한다.

  2) 자식 노드를 탐색한다.

    - 일반적인 DFS와는 다르게 방문했던 노드를 다시 방문하면 안된다.

 

2. 현재 노드의 자식 노드에서 얻을 수 있는 값을 DP 테이블에 반영한다.

  1) 현재 마을이 우수 마을인 경우 자식 노드는 무조건 일반 마을이어야 한다.

    - dp[1][cur] += dp[0][next];

 

  2) 현재 마을이 일반 마을일 경우, 자식 노드는 일반 마을/우수 마을이 될 수 있다.

    - dp[0][cur] += MAX(dp[0][next], dp[1][next]);

 

3. 갱신하다 보면 최상단 노드 데이터가 정답이 된다.

  1) dp[0][1], dp[1][1] 중 큰 값을 정답으로 출력한다.

 

 

예제 입력으로 그림 예시를 들어보았다.

 

7

1000 3000 4000 1000 2000 2000 7000

1 2

2 3

4 3

4 5

6 2

6 7

 

아래 그림에서 각 노드의 숫자가 의미하는 숫자는 위부터 차례대로 노드 번호, dp[0](일반), dp[1](우수마을)이다.

 

dp[0]은 하위 노드의 dp[0], dp[1] 중 큰 값을 더하고,

dp[1]은 하위 노드의 dp[0]을 더해준다.

 

 

 

 

3. 소스코드

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

vector<int> cnt;
vector<int> node[10001];
bool visit[10001] = { false, };
int dp[2][10001] = { 0, };

// Tree DP 구성
void dfs(int cur) {

	if (visit[cur]) {
		return;
	}

	// 초기값 정의
	// dp[0][idx] : 일반 마을
	// dp[1][idx] : 우수 마을
	visit[cur] = true;
	dp[0][cur] = 0;
	dp[1][cur] = cnt[cur];

	for (int next : node[cur]) {
		if (visit[next]) continue;

		dfs(next);
		dp[0][cur] += MAX(dp[0][next], dp[1][next]);
		dp[1][cur] += dp[0][next];
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	cnt.push_back(0);

	for (int i = 0, input; i < n; i++) {
		cin >> input;
		cnt.push_back(input);
	}

	for (int i = 0, a, b; i < n; i++) {
		cin >> a >> b;
		node[a].push_back(b);
		node[b].push_back(a);
	}

	dfs(1);

	cout << (MAX(dp[0][1], dp[1][1])) << "\n";

	return 0;
}