[백준/BOJ] 백준 1949번 : 우수 마을

www.acmicpc.net/problem/1949

1949번: 우수 마을

트리DP(트리에서 다이나믹 프로그래밍)을 통해 문제를 해결했으며 cache[노드 번호][우수마을인지 아닌지][이전마을이 우수마을인지 아닌지]를 통해 문제를 해결했다. 유의할 점은 here이 우수마을이 아닌데, 이전 마을도 우수마을이 아니었을 경우이다 이때 there한곳은 무조건 우수마을이어야 하는데 자동적으로 there이 우수마을인 경우가 최적이 되는 경우에는 상관없지만 그렇지 않다면 우수마을로 선택했을 때 손해가 가장 적은 there한곳은 무조건 우수마을로 골라야 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> people(10001, 0);
vector<int> adj[10001];
vector<int> maked(10001, 0);
int cache[10001][2][2];

void Pre()
{
	for (int i = 0; i < 10001; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				cache[i][j][k] = -1;
}

struct node {
	int number;
	int human;
	vector<node*> children;
};

//루트노드가 here인 트리 만들기
node* Make_tree(int here)
{
	node* root = new node();
	root->number = here;
	root->human = people[here];
	maked[here] = 1;

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		if (maked[there] == 1) //there 노드를 이미 만들었을때
			continue;

		root->children.push_back(Make_tree(there));
	}

	return root;
}


//here가 (check=0 우수마을X, check=1 우수마을O), (before=0 이전마을 우수마을X, before=1 이전마을 우수마을O)일때 here가 루트노드인 서브트리 주민수의 최대 합 
int Solve(node* here, int check, int before)
{
	int& ret = cache[here->number][check][before];

	if (ret != -1)
		return ret;

	ret = 0;

	//here 우수 마을이 아닐때
	if (check == 0)
	{
		//here 이전 노드가 우수 마을이 아니었을때
		//there 한곳은 우수마을이어야 된다
		//우수마을로 선택했을때 손해가 가장 작은 there 한곳은 무조건 우수 마을로 고른다
		if (before == 0)
		{
			bool select_find = false;
			int diff_min = 987654321;

			for (int i = 0; i < here->children.size(); i++)
			{
				node* there = (here->children)[i];

				int diff = Solve(there, 1, 0) - Solve(there, 0, 0); // there를 우수마을로 골랐을때와, 안골랐을때의 차이

				if (diff >= 0) //우수마을로 고른게 더 작지 않다면 우수마을로 고른다 (자동적으로 우수마을이 골라지는 경우)
				{
					select_find = true;
				}

				else //우수 마을로 고르지 않은게 더 크다면 (diff가 음수일때)
				{
					//가장 작은 차이를 저장한다 (손해를 제일 적게 하기 위해)
					if (diff_min > diff)
					{
						diff_min = diff;
					}
				}

				ret += max(Solve(there, 1, 0), Solve(there, 0, 0));
			}

			if (select_find == false && diff_min != 987654321) //자동적으로 우수마을로 골라지는게 없었을때, 손실이 최소되는 우수마을을 고른다(최소 손실을 반영한다)
			{
				ret += diff_min; //손실 반영
			}
		}

		//here 이전 노드가 우수 마을이었을때
		//there는 우수마을이든 아니든 상관 없다
		else if (before == 1)
		{
			for (int i = 0; i < here->children.size(); i++)
			{
				node* there = (here->children)[i];

				ret += max(Solve(there, 0, 0), Solve(there, 1, 0));
			}
		}
	}

	//here가 우수마을 일때
	else if (check == 1)
	{
		ret += here->human;

		for (int i = 0; i < here->children.size(); i++)
		{
			node* there = (here->children)[i];

			//인접한곳은 모두 우수마을이 아니다
			ret += Solve(there, 0, 1);
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		people[i] = input;
	}

	for (int i = 0; i < n - 1; i++)
	{
		int u, v;

		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	//루트가 1인 트리로 만들기
	node* tree = Make_tree(1);

	//루트노드를 우수마을로 고르지 않을때와 고를때중 큰값 구하기
	cout << max(Solve(tree, 0, 0), Solve(tree, 1, 0));

	return 0;
}