골드1 - 백준 1949 우수 마을

백준 1949 우수 마을

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

접근방식

답을 구하기 위해서는 인접하지 않은 마을을 선택하여 최대값을 구해야한다. 만약 마을이 일렬로 있다면 단순하게 DP를 사용하여 마을을 선택하면 되지만 마을이 트리 구조로 되어있기 때문에 고려해야할 부분이 있었다.

한 마을에 여러 개의 마을이 연결되어 있을 때, DP를 어떻게 처리할 것인지 고민했고, 현재의 마을을 선택했을 때와 선택하지 않았을 때로 나누어서 생각했다.
현재의 마을이 선택되었을 때, 현재 마을과 인접한 마을들은 선택이 될 수 없고, 각 인접 마을들이 선택되지 않았을 때 나올 수 있는 각각의 가장 큰 값들을 더해주어 결과를 저장했고, 반대의 경우인 현재의 마을을 선택하지 않았을 때의 경우도 계산하여 결과를 저장했다.

이렇게 차근차근 리프 노드부터 올라가면서 최대값을 더해주었고 루트까지 올라갔을 때 전체 마을의 최대값을 구할 수 있었다.

풀이

리프 노드부터 거슬러 올라가기 위해 재귀를 이용하였다. 재귀 함수 dfs 내의 반복문에서 연결된 노드들을 방문하며 최대값들을 구해주었고, 두 가지 경우로 나누어 각각 합을 저장하였다.
현재 노드를 선택하였을 경우는 인접 노드는 절대 선택할 수 없어서 따로 고려해 줄 필요없이 non_select_sum을 더해주었다.
반면 현재 노드를 선택하지 않은 경우는 인접 노드가 선택될 수도, 안될 수도 있기 때문에 서로 값을 비교하여 큰 경우를 더해주었다.

모든 인접 노드에 대해서 최대값을 계산해주면 선택, 미선택 두 가지의 최대값을 저장한 selection 클래스를 리턴해주었다.

메인 함수에서는 dfs 함수로부터 리턴 받은 selection 클래스의 변수값을 비교해주어 큰 값을 출력해준다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int value[10001];
bool visited[10001];
vector<vector<int>> link;

class selection
{
public:
	int select_sum;
	int non_select_sum;

	selection(int ss, int nss)
	{
		this->select_sum = ss;
		this->non_select_sum = nss;
	}
};

selection dfs(int n)
{
	int sum = value[n];
	int non_sum = 0;

	for (int i = 0; i < link[n].size(); i++)
	{
		if (visited[link[n][i]])
			continue;

		visited[link[n][i]] = true;
		selection sel = dfs(link[n][i]);

		// 현재 노드 선택
		sum += sel.non_select_sum;

		// 현재 노드 미선택
		if (sel.non_select_sum > sel.select_sum)
			non_sum += sel.non_select_sum;
		else
			non_sum += sel.select_sum;
	}
	
	selection result = selection(sum, non_sum);
	return result;
}

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

	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		vector<int> temp;
		link.push_back(temp);
		cin >> value[i];
		if (i == N)
			link.push_back(temp);
	}

	for (int i = 0; i < N - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		link[a].push_back(b);
		link[b].push_back(a);
	}

	visited[1] = true;
	selection answer = dfs(1);

	cout << max(answer.select_sum, answer.non_select_sum) << endl;

	return 0;
}