백준 15900번 나무 탈출 C++

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

 

리프 노드에 있는 말을 한 칸씩 올려서 루트 노드에 말이 도착하면 말이 사라지고, 모든 말이 사라짐과 동시에 차례가 끝난 사람이 이기는 게임이다.

생각을 조금 해보면 자기 차례때 어느 말을 선택하든 결과는 달라지지 않고, 단지 먼저 누가 시작했는지에 따라 승패가 정해지는 홀짝 게임 같은 게임이다.

 

결국 루트 노드에서 리프 노드까지의 모든 높이의 합에 따라 승패가 결정된다.

dfs를 통해서 루트 노드에서 모든 리프 노드까지의 합을 구하고, 그 합이 홀수라면 성원이의 승리고, 짝수라면 성원이의 패배이다.

 

리프 노드와 연결된 노드는 무조건 하나이기 때문에 노드와 연결된 노드가 1개이고, 그 노드가 1이 아닐 때 (1은 루트노드라고 문제에 적혀있음) 를 dfs의 종료 조건으로 설정하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n;
int sum = 0;
vector<vector<int>> node(500001, vector<int>());
vector<bool> visited(500001,false);

void dfs(int num, int cnt) {
	if (node[num].size() == 1 && num != 1) {
		sum += cnt;
		return;
	}
	visited[num] = true;
	for (int i = 0; i < node[num].size(); i++) {
		if (visited[node[num][i]]) continue;
		dfs(node[num][i], cnt + 1);
	}
}

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

	cin >> n;
	int node1, node2;
	for (int i = 0; i < n - 1; i++) {
		cin >> node1 >> node2;
		node[node1].push_back(node2);
		node[node2].push_back(node1);
	}
	dfs(1, 0);
	if (sum % 2 == 0) cout << "No";
	else cout << "Yes";
};