[C/C++] 백준 15900번 - 나무 탈출

 

<코드>

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

int N, u, v, cnt;
bool check[500001];
vector<int> tree[500001];
queue<int> q;

void dfs(int x, int depth)
{
	if (x != 1 && tree[x].size() == 1) // leaf node 일 때
	{
		if (depth % 2 == 1) cnt++;
		return;
	}

	for (int i = 0; i < tree[x].size(); i++)
	{
		if (check[x] == false)
		{
			check[x] = true;
			dfs(tree[x][i], depth + 1);
			check[x] = false;
		}
		
	}

}

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

	cin >> N;

	for (int i = 0; i < N - 1; i++)
	{
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}

	
	dfs(1, 0);

	if (cnt % 2 == 1) cout << "Yes";
	else cout << "No";

}

 

풀이 방법

 

루트노드부터 리프노드까지의 거리를 depth라고 할 때 dfs를 통해서 구한 depth가 모두 짝수일 경우 선으로 시작하는 성원이는 형석이를 이길 수 없다. 그러나 dfs를 통해서 구한 depth들 중에서 홀수의 개수가 1개가 있다면 게임을 이길 수 있게되지만 홀수의 개수가 짝수인 경우라면 게임을 이길 수 없게 된다.

 

즉, depth들 중에서 홀수인 수의 개수가 홀수개여야 성원이는 형석이를 이길 수 있다. 

 

 

 

 

www.acmicpc.net/problem/15900

15900번: 나무 탈출