개요

백준 1949번: 우수 마을

• 입력
  첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하이다. 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다.

• 출력
  첫째 줄에 '우수 마을'의 주민 수의 총 합을 출력한다.

접근방식

1. 트리를 만들고, 백준 12865: 평범한가방 문제에서 깨달았듯이,
   그리디가 아니라 모든 경우를 순회해야하고, 모든 케이스를 찾을 필요가 없는 최대값 구하기 유형이라 DP를 사용해야 한다는 건 알았다.

2. 하지만 노드들을 입력받고
   트리를 만들면서 동시에 dp를 진행하려하니 조건문이 여러개 붙고,
   또 조건 초기화를 하며 트리를 다시 돌리는식으로 구현했더니
   결국 너무 조잡해지고 디버깅도 어려워져서 결국 인터넷을 검색을 하였다.

3. 검색해본 결과 내가 시도한 것과 방향은 같지만
   일단 트리를 만들고, 그 후 dp를 실행하는 식으로 구현하였다.
   확실히 이런식으로 분리시키니 dp함수 작성할 때 고려할게 적어서 편했다.

전체 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//adj는 그래프, tree는 adj를 트리로 구현한 구조이다
vector<vector<int>> tree, adj;
//노드의 총 갯수
int N;
//각 마을의 인원수
vector<int> villageInfo;
//트리 만들때 사용되는 각 마을을 방문했는지 여부
vector<bool> visited;
//각 노드가 우수마을일 때/ 우수마을이 아닐때의 최댓 dp값
int dp[10'001][2];

void MakeTree(int Node);
int MaxGoodVillagePeople(int Node, bool isGood);

void Input() {
	int tmp = 0, tmpNode1=0, tmpNode2 = 0;
	cin >> N;
	// 각 벡터들 사이즈 할당해줌, []연산자 이용하기 위함
	adj.resize(N + 1);
	tree.resize(N + 1);
	visited.resize(N + 1);
	villageInfo.resize(N + 1);
	//각 마을의 인원수 저장
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		villageInfo[i]=(tmp);
	}
	//인접 노드 받아와서 양방향그래프 adj에 저장
	for (int i = 0; i < N - 1; i++) {
		cin >> tmpNode1 >> tmpNode2;
		adj[tmpNode1].push_back(tmpNode2);
		adj[tmpNode2].push_back(tmpNode1);
	}
	//아무노드인 tmpNode1을 루느노드로 하는 트리 구조 생성
	MakeTree(tmpNode1);
	//루트노드인 tmpNode1이 우수마을일때의 최대 인원수와 tmpNode1이 우수마을이 아닐때의 최대인원수중 더 큰값이 답
	int Ans = max(MaxGoodVillagePeople(tmpNode1, true), MaxGoodVillagePeople(tmpNode1, false));
	cout << Ans;
}

/// <summary>
/// tree만드는 함수
/// </summary>
/// <param name="Node"></param>
void MakeTree(int Node) {
	visited[Node] = true;

	for (int elem : adj[Node]) {
		if (visited[elem]) continue;
		//트리 구조의 부모값에 자식값 대응시키고 재귀
		tree[Node].push_back(elem);
		MakeTree(elem);
	}
}
/// <summary>
/// 각 서브트리의 루트노드가 Node이고 Node마을이 우수한 마을이거나 아닐 때 
/// 해당 서브트리의 최대 우수마을인원값 재귀 통해 구하는 함수 
/// </summary>
/// <param name="Node(각 서브트리의 루트노드)"></param>
/// <param name="isGood(우수한 마을인지 bool형 변수)"></param>
/// <returns> 해당 서브트리에서의 최대 우수마을인원값 </returns>
int MaxGoodVillagePeople(int Node,bool isGood) {
	//이미 구한값이면 바로 return한다
	if (dp[Node][isGood]) return dp[Node][isGood];
	//참조자 &을 사용해 값을 바로 변경해줄수있도록 함
	int& ret = dp[Node][isGood];
	for (int elem : tree[Node]) {
		//기본적으로 elem노드가 우수마을이 아닐때 최대값을 불러오고
		int tmp = MaxGoodVillagePeople(elem, false);
		//만약 isGood이 false라면 elem노드가 우수마을일때 최대값과 비교해본다.
		if (!isGood) tmp = max(tmp, MaxGoodVillagePeople(elem, true));
		//각 자식마다 서브트리가 있을 것이므로 최대 인원값은 모든자식들의 최대값을 더한값이 나와야한다.
		ret += tmp;
	}
	//마지막에 isGood인지 체크하여 우수한마을이면 Node노드에 해당하는 인원수도 더하고 return해준다.
	if (isGood) ret += villageInfo[Node];
	return ret;
}

int main() {
	Input();
}

문풀후생

난 처음 생각했을 때 isGood뿐만아니라 wasGood변수까지 매개변수로 넣어서
해당 노드 이전값이 true였는지 false였는지 체크한 후,
isGood, wasGood이 둘 다 false일때 자식값에 true를 넣어주고 재귀시키고
wasGood이 true,isGood이 false라면 자식값이 true일때와 false일때를
둘 다 넣어주고 그 두 값 중 비교를 하는식으로 구현하였다.

따라서 왜 위 코드처럼 기본적으로 자식의 우수마을여부를 false로 정하고
지금 isGood이 false일때만 true값과 비교해주는 지 이해를 못했는 데,
생각해보니 당연한 것이였다.

의문이 든건 저렇게 비교를 하면 연결된 마을이
false,false,false인 상황도 나올텐데 오답이아닌가 이런생각이였는데,
어차피 false,false,false보단 false,true,false경우의 최대값이 무조건 클것이므로
애초에 false,false,flase값은 답이 될수가없다.

따라서 더 코드가 가독성있고 답도 정확히 나오므로 wasGood을 신경쓸 필요가 없었다.