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

https://www.acmicpc.net/problem/15900

 

 

#문제 간단 정리

그래프 문제

 

#문제 해결 방법

 

일단 그리디하게 트리의 깊이의 개수가

홀수면 성헌이가 이기고 짝수면진다

이건 몇번 실제로 그려보면 쉽게 알 수 있기 때문에

 

트리의 깊이를 확인하는걸 dfs나 그래프탐색으로 해주

 

#전체 코드

#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <algorithm>
#include <string>
#include <iomanip> 
#include <queue>
using namespace std;

vector<bool> visited;
vector<vector<int>> graph;
int gCount;

void dfs(int level, int node) {

    bool isLast = true;

    for (auto a : graph[node]) {
        if (!visited[a]) {
            visited[a] = true;
            dfs(level + 1, a);
            isLast = false;
        }
    }

    if (isLast) {
        gCount += level;
    }
    return;
}

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

    //각 리프노드에서 루트노드까지의 거리가 짝수면 성헌이가 지고 홀수면 이긴다.

    int n;
    cin >> n;


    visited.resize(n + 1, false);
    graph.resize(n + 1);
    gCount = 0;

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    visited[1] = true;
    dfs(0, 1);
    cout << gCount << '\n';
    if (gCount % 2 == 1)
        cout << "Yes\n";
    else
        cout << "No\n";
}