[C++] 백준 1949 우수 마을

문제 링크

---

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

1949번: 우수 마을

접근 방법

---

1. 문제에서 마을은 트리구조로 되어 있다고 얘기하고 있다. 즉 마을의 연결관계를 트리구조로 나타내자.

 

void dfs(int now, int parent) {
	for (int i = 0; i < adj[now].size(); i++) {
		int there = adj[now][i];
		if (parent != there) {
			tree[now].push_back(there);
			dfs(there, now);
		}
	}
}

DFS를 통해 트리구조를 구현할 수 있다. adj[]는 양 방향으로 인접한 노드에 대한 정보를 담고 있는 벡터이며,

인접한 부분을 탐색을 하되 if (parent != there)라는 조건을 통해 부모 방향으로 접근할 수 없게 자식 방향으로만 탐색하여 트리를 구성하게 된다.

 

 

문제에서 제시하는 3가지 조건

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

조건 1을 통해 동적계획법을 사용해야 한다는 사실을 깨달을 수 있다. 동적계획법을 하며 메모를 하기 위한 변수로는 

dp[now][in] (in=0 or in=1)을 사용할 것이며 now는 현재노드 번호, in은 현재 마을이 우수마을로 선정되었다면 1 아니면 0을 의미 한다. 

 

if (include) { //우수 마을이라면
	int ans = 0;
	for(int i = 0; i < tree[now].size(); i++) {
		int next = tree[now][i];
		ans += solve(next, 0);
	}
	return res = ans + cost[now];
}

solve() 함수 내에서 현재 노드가 우수마을로 선정되었을 경우이다. 2번 조건에 따라 다음 마을은 우수마을이 되면 안되므로 자식노드는 우수마을이 되지 않게 (solve(next, include = 0))진입한다. 또한 우수마을로 선정되었을 경우에는 

cost를 더하게 된다.

 

else { //include == 0
		int ans = 0;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			int t1 = solve(next, 1);
			int t2 = solve(next, 0);
			ans += max(t1, t2);
		}
		return res = ans;
	}

 이는 현재 노드가 우수마을로 선정되지 않았을 경우이다.

1. 우수마을로 선정되지 않은 경우로 진입을 하게 되는 경우는 이전의 노드가 우수마을이였을 경우가 있다.

2. 우수마을로 선정되지 않은 경우로 진입을 하게 되는 경우는 이전의 노드가 우수마을이 아니였을 경우가 있다.

 

1의 경우 다음 마을이 우수마을 이던지 아닌지 끝까지 탐색을 해보지 않으면 모른다. 하지만 2의 경우 다음 노드는 무조건 우수마을로 가는것이 이득이기 때문에 max에서 자동으로 우수마을로 가지 않는 값이 걸러질 것이다.

 

소스 코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 10000

using namespace std;

vector <int> adj[MAX + 1];
vector <int> tree[MAX + 1];
int dp[MAX + 1][2];
int cost[MAX + 1];

void dfs(int now, int parent) {
	for (int i = 0; i < adj[now].size(); i++) {
		int there = adj[now][i];
		if (parent != there) {
			tree[now].push_back(there);
			dfs(there, now);
		}
	}
}

int solve(int now, int include) {
	int &res = dp[now][include];
	if (res != -1) 
		return res;
	if (include) { //우수 마을이라면
		int ans = 0;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			ans += solve(next, 0);
		}
		return res = ans + cost[now];
	}
	else {
		int ans = 0;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			int t1 = solve(next, 1);
			int t2 = solve(next, 0);
			ans += max(t1, t2);
		}
		return res = ans;
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &cost[i]);
		dp[i][0] = dp[i][1] = -1;
	}
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, 1);
	int result = max(solve(1, 1), solve(1, 0));
	cout << result;
}

개발 환경 : VS2019

질문, 지적 환영합니다!