[BOJ 27915 // C++] 금광

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

 

이번에 볼 문제는 백준 27915번 문제인 금광이다.
문제는 아래 링크를 확인하자.

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

27915번: 금광

주어진 조건에 따라 문제에서 주어지는 금광은 1번 방을 루트로 하는 트리구조로 모델링할 수 있음을 알 수 있다.

 

모든 방은 1번 방으로부터 거리가 홀수인 방(O)과 짝수인 방(E) 둘로 구분할 수 있다. 이 때, 어떤 회사도 O에 해당하는 방을 둘 이상 채굴하거나 E에 해당하는 방을 둘 이상 채굴하는 것은 불가능함을 관찰하자. 또한, O에 해당하는 방 하나와 E에 해당하는 방을 골랐을 때 이 두 방 사이의 거리는 항상 홀수가 됨 또한 관찰하자.

 

위의 관찰을 이용하면 O에 해당하는 방의 개수와 E에 해당하는 방의 개수 중 더 큰 값이 문제의 답이 됨을 알 수 있다. 그래프 탐색 알고리즘등을 이용해 거리가 홀수인 방 및 짝수인 방의 개수를 구하고 문제를 해결하자.

 

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

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

int N;
vector<int> G[100001];
int cnt;

void dfs(int cur, int p) {
	if (p) cnt++;
	p ^= 1;
	for (auto& nxt : G[cur]) dfs(nxt, p);
}

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

	cin >> N;
	for (int n = 2; n <= N; n++) {
		int x; cin >> x;
		G[x].emplace_back(n);
	}

	dfs(1, 0);

	cout << max(cnt, N - cnt);
}