[백준]15900번: 나무 탈출

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

15900번: 나무 탈출

문제를 간단하게 요약하면 다음과 같다.

- 1은 루트 노드다.

- 초기 모든 리프 노드에만 말이 있다.

- 말이 루트 노드(1)에 도착하면 제거한다.

- 게임은 성원이가 먼저 시작하며 우리가 원하는건 성원이가 이기면 "Yes"를 지면 "No"를 출력하는 것이다.

 

접근 아이디어

- 몇 개의 트리를 그리고 시뮬레이션 해보면 다음과 같은 규칙을 발견할 수 있다.

- 루트노드에서 모든 리프 노드까지의 depth를 구해 이걸 다 합친다.

- 합친 값이 홀수면 성원이가 이기고 짝수면 진다.

- DFS를 통해 루트노드에서 리프까지 방문하면서 depth를 구해 다 더하고 최종 출력시 짝수 홀수를 판별한다.

#include<iostream>
#include<vector>

#define FastIO ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

using namespace std;

vector<vector<int>> trees;
vector<bool> visited;

int treeTotalDepth = 0;

void DFS(int start, int depth)
{
	// 리프 노드인 경우
	if (trees[start].size() == 1 && start != 1)
	{
		treeTotalDepth += depth;
		return;
	}
	for (int i = 0; i < trees[start].size(); i++)
	{
		if (!visited[trees[start][i]])
		{
			visited[trees[start][i]] = true;
			DFS(trees[start][i], depth + 1);
			visited[trees[start][i]] = false;
		}
	}
}

int main(void)
{
	FastIO;

	int N = 0; // 트리의 정점 개수 N
	cin >> N;
	trees.resize(N + 1);
	visited.resize(N + 1, false);

	int a = 0, b = 0; // a와 b 노드 사이의 간선
	for (int i = 0; i < N - 1; i++)
	{
		cin >> a >> b;
		trees[a].push_back(b);
		trees[b].push_back(a);
	}
	visited[1] = true;
	DFS(1, 0);

	if (treeTotalDepth % 2 == 1)
		cout << "Yes" << "\n";
	else
		cout << "No" << "\n";

	return 0;
}