취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5934번 문제인 Visiting Cows이다.
문제는 아래 링크를 확인하자.

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

문제 설명에 따라, 모든 친구 소들은 트리모양의 그래프 위에 살고 있다.

서로 인접한 두 소를 고르지 않게 가장 많은 소를 세어주자.

dfs를 하면서 각 노드 K마다 K를 루트로 하는 서브트리에서 (K를 고를 때의 최댓값)과 (K를 고르지 않을 때의 최댓값) 둘을 인자로 계속 넘겨받아 문제를 해결하자.

아래는 제출한 소스코드이다.

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

vector<int> G[50001];

pair<int, int> dfs(int cur, int par) { // {지금 보는 소 방문시, 지금 보는 소 미방문시}
	int ret0 = 0, ret1 = 1;
	for (auto node : G[cur]) {
		if (node == par) continue;
		auto p = dfs(node, cur);
		ret0 += max(p.first, p.second);
		ret1 += p.second;
	}

	return make_pair(ret1, ret0);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	auto p = dfs(1, 1);

	cout << max(p.first, p.second);
}