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

문제링크 : https://www.acmicpc.net/problem/15900

15900번: 나무 탈출

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, sum;
vector<int>tree[500001];
bool visited[500001];

void dfs(int n, int cnt)
{
    if(n!=1 && tree[n].size()==1) //리프노트라면
    {
        sum+=cnt; //깊이 저장
        return;
    }

    for(int i=0; i<tree[n].size(); i++)
    {
        if(visited[n]) continue;
        visited[n]=true;
        dfs(tree[n][i], cnt+1);
        visited[n]=false; //부모로 돌아가서 다음 자식 탐색
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    cin >> N;
    for(int i=0; i<N-1; i++)
    {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1, 0); //루트 1
    cout << (sum%2==1 ? "Yes" : "No");
    
}

 

2명이서 번갈아가며 게임말을 움직이기 때문에 먼저 시작하는 사람 기준 모든 깊이의 합(총 움직이는 수)이 홀수면 선턴이 이기고 아니면 후턴이 이긴다.

 

루트는 1이기에 1을 기준으로 연결된 값을 탐색한다.

현재 값을 방문처리하고, 연결된 다음 값과 늘어난 깊이 1를 같이 넘겨준다.

그리고 부모에 연결된 또다른 값을 탐색하기 위해 위 dfs 문 바로 밑줄에 방문처리했던 부모를 다시 풀어준다.

 

이를 현재 노드가 리프노드일때까지 반복하며, 리프노드일때 누적한 cnt를 합에 더해주고 이 합이 홀수인지 짝수인지 판별하여 답을 출력한다.