문제 : 백준 15900 나무 탈출 🪵
난이도 : 실버 1
1️⃣ '나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다.
2️⃣ 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직인다.
3️⃣ 만약 그 게임말이 루트 노드에 도착했다면, 그 게임말을 즉시 제거한다.
4️⃣ 게임말이 게임판에 존재하지 않아 고를 수 없는 사람이 지게 된다.
5️⃣ 성원이가 먼저 시작하고 형석이가 나중에 시작한다.
6️⃣ 성원이가 이 게임을 이길 수 있다면 Yes를 질 수 있다면 No를 출력한다.
☝️이때, 리프노드에 말이 각각 있으므로 모든 리프 노드의 말을 1번 노드(루트 노드)까지 옮겨야 한다.
따라서, 각각 리프 노드부터 1번 노드(루트 노드)까지의 거리인 Depth 깊이가 해당 말을 옮겨야 하는 횟수이다.
그러므로 모든 말이 없어질 때까지 옮기는 횟수는 모든 말을 1번 노드까지 옮기는 횟수인 모든 리프 노드의 깊이의 합이다.
성원 ➡️ 형석 순서대로 번갈아서 말을 옮기므로, 성원은 홀수 번째에 말을 옮긴다.
이때, 모든 말이 없어질 때까지 옮기는 횟수의 합 = 홀수인 경우, 성원이가 마지막으로 말을 옮기므로 성원이가 이기게 된다.
그러나, 짝수인 경우 형석이가 마지막으로 말을 옮기므로 형석이가 이기게 된다.
vector<int> graph[500001];
for(int i=0; i<N-1; i++){
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
unordered_map<int, int> depth; //해당 노드의 번호, 깊이
unordered_map<int, bool> check; //방문 여부
int leapDepthSum = 0;
void dfs(int here){
check[here] = true;
bool leapCheck = true; //leap인지 확인
for(int i=0; i<graph[here].size(); i++){
if(!check[graph[here][i]]){
leapCheck = false;
depth[graph[here][i]] = depth[here]+1;
dfs(graph[here][i]);
}
}
if(leapCheck){
leapDepthSum += depth[here];
}
}
...
depth[1] = 0;
dfs(1);
if(leapDepthSum % 2 == 0){
cout<<"No"<<"\n";
}
else{
cout<<"Yes"<<"\n";
}
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> graph[500001];
unordered_map<int, int> depth; //해당 노드의 번호, 깊이
unordered_map<int, bool> check; //방문 여부
int leapDepthSum = 0;
void dfs(int here){
check[here] = true;
bool leapCheck = true; //leap인지 확인
for(int i=0; i<graph[here].size(); i++){
if(!check[graph[here][i]]){
leapCheck = false;
depth[graph[here][i]] = depth[here]+1;
dfs(graph[here][i]);
}
}
if(leapCheck){
leapDepthSum += depth[here];
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N = 0; //트리의 정점 개수
int a = 0, b = 0; //트리의 간선 정보
cin>>N;
for(int i=0; i<N-1; i++){
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
depth[1] = 0;
dfs(1);
if(leapDepthSum % 2 == 0){
cout<<"No"<<"\n";
}
else{
cout<<"Yes"<<"\n";
}
}