백준 1949 우수마을 C++ - DFS,DP , TREE

최대 1만개의 마을에서 우수 마을을 선정하는 문제이다.

 

조건은 다음과 같다.

1. 자신을 포함하여 인접마을 중 적어도 하나는 우수마을이어야 한다.

2. 우수마을끼리는 인접할 수 없다.

3. 트리구조로 되어 N개의 마을과 N-1개의 도로가 있다.

 

목표는 다음과 같다.

1. 인구를 최대로 해야 한다.

 

인구를 최대로 할 수 있으면서 조건에 맞춰야하므로 경우의 수를 따져서 탐색해봐야한다.

BFS로 접근하기 힘든 문제이므로 DFS를 통해 뽑거나 안뽑는 경우를 나눠 탐색한다.

 

먼저 다행히 트리구조이므로 순환하는 도로는 없다.

트리구조는 어느 node를 시작점으로 잡아도 트리 모양으로 이루어져 있으니 Root를 1로 두고 접근하였다.

 

먼저 인구 정보를 POP에, 연결된 도로 정보를 vector인 road에 저장한다.

그 후 1번 node를 기준으로 단방향 트리를 구성한다.(makeTree);

 

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &POP[i]);
	}
	for (int i = 0; i < N-1; i++) {
		int a, d;
		scanf("%d %d", &a, &d);
		road[a].push_back(d);
		road[d].push_back(a);
	}
	int ans = solve();
	printf("%d", ans);
	return 0;
}
//1번=root
void makeTree(int node) {
	
	for (int i = 0; i < road[node].size(); i++) {
		int nextnode = road[node][i];
		if (used[nextnode] == 0) {
			used[nextnode] = 1;
			tree[node].push_back(nextnode);
			makeTree(nextnode);
		}
	}
}

그 후 dp배열을 이용한다.

dp 배열의 의미는 특정 node에서 자신을 포함한 자식 노드들을 선택해서 얻을 수 있는 최대 인구수이다.

즉, dp[1][false]의 의미는 1번 노드를 우수마을로 선정하지 않았을 경우(false)얻을 수 있는 최대값을 의미하고,

dp[1][true]는 1번 마을을 선정했을 경우 얻을 수 있는 최대값을 뜻한다.

 

int dp[10001][2];
int dfs(int node, bool choosed) {
	if (dp[node][choosed]) {
		return dp[node][choosed];
	}
	int ret = 0;
	
	for (int i = 0; i < tree[node].size(); i++) {
		int nextnode = tree[node][i];
		//뽑든 안뽑든 다음건 안뽑을 수 있음
		int case1 = dfs(nextnode, false);
		int case2 = 0;
		//안뽑았다면 다음건 뽑을 수 있음
		if (!choosed) {
			case2 = dfs(nextnode, true);
		}	
		//단 연속으로 안뽑는경우(3마을이상) 무조건 작은 값을 가지므로 생각하지 않음
		ret += max(case1, case2);
	}
	if (choosed) {
		ret += POP[node];
	}
	return dp[node][choosed]=ret;
}

이미 그 마을에서의 최대값을 알고 있다면 (dp[node][choosed]값이 있다면) 바로 return 하며 종료한다.

없을 경우 최대값을 구해야한다.

 

case는 두 가지로 나뉜다.

1. 이번 마을을 선정할 경우 - 다음 마을은 무조건 선정할 수 없다.(dfs(nextnode,false))

2. 선정하지 않을 경우 - 다음 마을은 선정하거나, 선정하지 않을 수 있다.(dfs(nextnode,true))

 

만약 1-2-3-4-5 라는 1자 트리가 있을 경우 2,3,4를 연속으로 선택하지 않을 수도 있지만,

항상 최대로 선정하는 경우보다 작기 때문에 생각하지 않아도 된다.

 

case 두 가지 중 더 큰 값을 dp 배열에 저장하고 return 한다.

 

작동은 트리의 잎부분(가장 끝)까지 내려가 dp를 저장하고 차차 상위 노드로 올라오면서 dp배열을 형성하는 식이다.

 

전체코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int POP[10001];
int used[10001];
vector<int> road[10001], tree[10001];
int dp[10001][2];
int dfs(int node, bool choosed) {
	if (dp[node][choosed]) {
		return dp[node][choosed];
	}
	int ret = 0;
	
	for (int i = 0; i < tree[node].size(); i++) {
		int nextnode = tree[node][i];
		//뽑든 안뽑든 다음건 안뽑을 수 있음
		int case1 = dfs(nextnode, false);
		int case2 = 0;
		//안뽑았다면 다음건 뽑을 수 있음
		if (!choosed) {
			case2 = dfs(nextnode, true);
		}	
		//단 연속으로 안뽑는경우(3마을이상) 무조건 작은 값을 가지므로 생각하지 않음
		ret += max(case1, case2);
	}
	if (choosed) {
		ret += POP[node];
	}
	return dp[node][choosed]=ret;
}

//1번=root
void makeTree(int node) {
	
	for (int i = 0; i < road[node].size(); i++) {
		int nextnode = road[node][i];
		if (used[nextnode] == 0) {
			used[nextnode] = 1;
			tree[node].push_back(nextnode);
			makeTree(nextnode);
		}
	}
}
int solve() {
	used[1] = true;
	makeTree(1);
	int ret = max(dfs(1, 0), dfs(1, 1));
	return ret;
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &POP[i]);
	}
	for (int i = 0; i < N-1; i++) {
		int a, d;
		scanf("%d %d", &a, &d);
		road[a].push_back(d);
		road[d].push_back(a);
	}
	int ans = solve();
	printf("%d", ans);
	return 0;
}

 

solve()함수에서 dfs(1,0) 과 dfs(1,1)을 해줘 root 를 골랐을 경우와 안골랐을 경우를 따로 생각해준다.

 

 

cf) dp 배열과 dfs를 적용해야하는 고급 문제인 것 같다. 

dp배열로 접근할 때 말로 생각하면 쉬운 것 같다.

예를 들어, 위에 설명한 것처럼 dp[1]은 1번 노드에서 가질 수 있는 최대 인구수라고 정의하고

그 다음 만들어서 생성하는 습관을 들이면 dp배열을 쉽게 접근할 수 있을 것 같다.

 

추가로, dfs도 마찬가지. 선택하거나- 안하거나 둘의 경우를 각각 dfs로 접근한다고 생각하고 접근하자.