15900 나무 탈출

어떻게 풀지 그려봤을 때 트리의 높이의 합이 짝수면 형석이가 이기고 홀수면 성원이가 이긴다. 그래서 트리의 높이를 구하는 게 관건인데..

 

생각 1

bfs를 쓰자 

안 써서 써보고 싶었음.. 하지만 bfs를 쓰면 리프노드를 못 찾으니 리프노드까지의 길이를 알지 못한다.

 

생각 2

dfs 다음 노드가 존재하지 않으면 리프노드란 뜻이므로 리프노드를 찾을 수 있다. 그럼 리프노드의 길이의 합을 구할 수 있다

 

생각 3

그런데 이거 리프노드 길이의 합으로 생각 안 하고 그냥 전체 edge의 개수라고 생각하면 되지 않나??? 줄 수 세면 되는 거 아냐???? 

 

 

아니었다고 한다

 

 

--미완--

음... size가 0인거 출력해보니 1이 나온다. 왜지?? 나중에 찾아보기로

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

vector<int> adj[500005];
bool visited[500005];
int heightSum = 0;

void dfs(int curr, int h)
{
    visited[curr] = true;

    bool leaf = true;
    for (int next : adj[curr])
    {
        if (!visited[next])
        {
            leaf = false;
            dfs(next, h + 1);
        }
    }
    if (leaf)
        heightSum += h;
}

int     main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    memset(visited, false, sizeof(visited));
    dfs(1, 0);

    if (heightSum % 2 == 0)
        printf("No\n");
    else
        printf("Yes\n");

    return 0;
}

단방향 그래프여서 문제였다. 양방향으로 바꾸고 리프노드인지 확인해서 높이 더해줬다. 그랬더니 풀렸음! 알고보니 이 문제 전에 풀었던 문제였다. 실력.., 녹슬고 있구나..,