2-8. 트리 [BOJ 15900번]

1. 관련 문제 🎯

문제 : 백준 15900 나무 탈출 🪵
난이도 : 실버 1

2. 문제 소개 🧩

1️⃣ '나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다.

• 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다.
• 1번 정점은 '루트 노드', 자식이 없는 노드는 '리프 노드' 라고 불린다.

2️⃣ 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직인다.

• 처음에는 트리의 모든 리프 노드에 게임말이 하나씩 놓여있는 채로 시작한다.
• 어떤 사람의 차례가 오면, 그 사람은 현재 존재하는 게임말 중 아무거나 하나를 골라 그 말이 놓여있던 노드의 부모 노드로 옮긴다.
• 이 과정에서 한 노드에 여러 개의 게임말이 놓이게 될 수도 있다.

3️⃣ 만약 그 게임말이 루트 노드에 도착했다면, 그 게임말을 즉시 제거한다.

4️⃣ 게임말이 게임판에 존재하지 않아 고를 수 없는 사람이 지게 된다.

5️⃣ 성원이가 먼저 시작하고 형석이가 나중에 시작한다.

6️⃣ 성원이가 이 게임을 이길 수 있다면 Yes를 질 수 있다면 No를 출력한다.

3. 문제 풀이 🖌️

☝️이때, 리프노드에 말이 각각 있으므로 모든 리프 노드의 말을 1번 노드(루트 노드)까지 옮겨야 한다.
따라서, 각각 리프 노드부터 1번 노드(루트 노드)까지의 거리인 Depth 깊이가 해당 말을 옮겨야 하는 횟수이다.
그러므로 모든 말이 없어질 때까지 옮기는 횟수는 모든 말을 1번 노드까지 옮기는 횟수인 모든 리프 노드의 깊이의 합이다.

성원 ➡️ 형석 순서대로 번갈아서 말을 옮기므로, 성원은 홀수 번째에 말을 옮긴다.
이때, 모든 말이 없어질 때까지 옮기는 횟수의 합 = 홀수인 경우, 성원이가 마지막으로 말을 옮기므로 성원이가 이기게 된다.
그러나, 짝수인 경우 형석이가 마지막으로 말을 옮기므로 형석이가 이기게 된다.

3-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);
}

3-2. DFS를 사용하여 각각 리프 노드의 깊이를 모두 합한다.

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);

3-3. 모든 리프 노드 깊이의 합이 홀수인 경우, 성원이가 이긴다.

if(leapDepthSum % 2 == 0){
	cout<<"No"<<"\n";
}
else{
	cout<<"Yes"<<"\n";
}

4. 전체 코드 🔑

#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";
    }
}

5. 결과 🏆