BOJ 15900 : 나무 탈출

• 문제 링크 : boj.kr/15900
• 난이도 : S1
• 태그 : 트리, BFS

15900번: 나무 탈출

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    vector<vector<int>> edge(n+1, vector<int>());
    for(int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        edge[a].emplace_back(b);
        edge[b].emplace_back(a);
    }

    vector<bool> visit(n+1, false);

    int ans = 0;
    queue<pii> _q;
    _q.push({1, 0});
    visit[1] = true;
    while(!_q.empty()) {
        pii cur = _q.front(); _q.pop();
        int cnt = 0;
        for(auto u : edge[cur.first]) {
            if(visit[u]) continue;
            _q.push({u, cur.second + 1});
            visit[u] = true;
            cnt++;
        }
        if(!cnt) {
            ans += cur.second;
        }
    }
    cout << (ans % 2 ? "Yes" : "No");
    return 0;
}

---

풀이

게임에 대해서 살펴보자.

 

어떤 하나의 말을 움직이는 방법은 한 가지 밖에 없다. 또한 하나의 말을 움직이더라도 다른 말의 움직임에 영향을 주지 않는다. 따라서 말을 움직이는 순서는 중요하지 않다.

말을 움직이는 순서가 중요하지 않다는 것은, 게임의 승패가 말을 움직이는 횟수에 달려 있다는 것과 같다.

 

이제 말을 움직이는 횟수를 구해보자.

하나의 말을 움직일 수 있는 횟수는 루트노드까지의 거리와 같다. 따라서 루트노드로부터 탐색을 통해 리프 노드까지의 거리를 구하여 말을 움직이는 횟수를 구할 수 있다.

 

성원이부터 게임을 시작하므로 말을 움직이는 횟수의 합이 홀수라면 성원이가, 짝수라면 형석이가 이기게 된다.