[백준 15900] - 나무 탈출(C++)

📕문제

---

평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출'이라는 보드게임이다.

'나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드'라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드'라고 불린다.

이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임 말이 하나씩 놓여있는 채로 시작한다. 어떤 사람의 차례가 오면, 그 사람은 현재 존재하는 게임 말 중 아무거나 하나를 골라 그 말이 놓여있던 노드의 부모 노드로 옮긴다. 이 과정에서 한 노드에 여러 개의 게임 말이 놓이게 될 수도 있다. 이렇게 옮긴 후에 만약 그 게임 말이 루트 노드에 도착했다면 그 게임 말을 즉시 제거한다. 모든 과정을 마치면 다음 사람에게 차례를 넘긴다. 이런 식으로 계속 진행하다가 게임 말이 게임판에 존재하지 않아 고를 수 없는 사람이 지게 된다.

성원이를 얕본 형석이는 쿨하게 이 게임의 선을 성원이에게 줘버렸다. 따라서 성원이가 먼저 시작하고 형석이가 나중에 시작한다. 그동안 형석이와 대결을 하면 매번 지기만 했던 성원이는 마음속에 분노가 가득 쌓였다. 이번 대결에서는 반드시 이겨서 형석이의 코를 꺾어주고 싶다. 그래서 게임을 시작하기 전에 게임판의 모양만 보고 이 게임을 이길 수 있을지 미리 알아보고 싶어졌다. 성원이가 이 게임을 이길 수 있을지 없을지를 알려주는 프로그램을 만들어 성원이를 도와주자

 

📕입력

---

첫째 줄에 트리의 정점 개수 N(2 ≤ N ≤ 500,000)이 주어진다.

둘째 줄부터 N-1줄에 걸쳐 트리의 간선 정보가 주어진다. 줄마다 두개의 자연수 a, b(1 ≤ a, b ≤ N, a ≠ b)가 주어지는데, 이는 a와 b 사이에 간선이 존재한다는 뜻이다.

📕출력

---

성원이가 최선을 다했을 때 이 게임을 이길 수 있으면 Yes, 아니면 No를 출력한다.

🔎문제 해석

---

문제가 굉장히 길어서 복잡해보이지만 해석하면 간단하다.

문제를 요약해보면

1. 1번노드는 루트 노드.
2. 우리가 흔히 알고 있는 리프 노드의 개수가 장기짝의 개수다.
3. 맨 마지막 말이 부모노드에 도착한 시점에 다음 차례에 사람이 게임을 지게 된다.
4. 우리의 주인공이 선공이다. [성원이 파이팅]

그럼 주인공이 이기기 위해서의 경우의 수를 계산해보면

장기말 수	이동횟수	결과
짝	짝	패
짝	홀	승
홀	짝	패
홀	홀	승

경우의 수를 계산해보면 알 수 있는 것처럼 이동 횟수가 홀수면 선공이 이기고, 짝수면 후공이 이기는 것을 알 수 있다.

그래서 우리는 이동 횟수만 알면 된다.

이동 횟수는 부모 노드에서 각 리프 노드까지의 depth가 될 것이다.

나는 dfs를 사용해서 풀었다.

이 지점이 리프 노드인지에 대한 검사는 1번 노드가 아니고, 연결된 간선의 수가 1개이면, 그 지점은 리프 노드이다.

 

💻코드

/*
15900 실버1 나무탈출
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int n;
vector<int> graph[500001];
vector<int> visit;
void dfs(int x, int detph);
int cnt = 0;
int height = 0;
int main()
{
    int start, finish;
    cin >> n;
    visit.resize(n + 1);
    for (int i = 0; i < n - 1; i++)
    {
        cin >> start >> finish;
        graph[start].push_back(finish);
        graph[finish].push_back(start);
    }
    dfs(1, 0);
    if (height % 2 == 1)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}
void dfs(int x, int depth)
{
    visit[x] = 1;
    if (x != 1 && graph[x].size() == 1) //현재 들어온 지점이 리프노드일때임.
    // 즉 출발점이 아니고 간선이 하나일때.
    {
        cnt++; //리프 노드 갯수 +
        height += depth; //그때의 말 이동횟수를 저장.
        return;
    }
    for (int i = 0; i < graph[x].size(); i++)
    {
        if (visit[graph[x][i]] != 0) //이미 방문한 좌표라면 넘어감!
        {
            continue;
        }
        visit[graph[x][i]] = 1; //방문처리
        dfs(graph[x][i], depth + 1); 
    }
}

 

 

✔느낀 점

• 진짜 계속 BFS로만 풀다가 갑자기 DFS로 풀려고 하니까 뇌가 정지했다.
• 둘 다 익숙해져야 하는데,,,
• 선공이 이기는 경우의 수를 잘 구한건지 모르겠는데, 내가 구한 방법으로는 저 경우의수 말고는 없던 것 같다!