[BOJ알고리즘, C++]#15900_나무 탈출, DFS, 깊이 우선 탐색

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 트리

[자료구조]#5_트리

트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리 자료구조의 노드 간 연결 관계는 간선을 통해 나타내며, 순환 구조를 형성하지 않아 계층 구조가 형성됩니다.

 

2. DFS

[자료구조]#6_그래프

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. DFS는 출발 정점으로부터 더 이상 확장 불가능한 단말 노드에 이르기까지 깊이 우선적으로 탐색하는 방법입니다. DFS는 일반적으로 재귀 호출 혹은 스택 자료구조를 통해 구현합니다. 

 

3. DP 활용은 실패, DFS를 활용하자!

1. DP와 DFS는 상호 보완 체제로 보인다. DP를 활용했지만, 구현이 어려워지는 것을 느끼고 DFS를 활용하자 성공했다.
2. DFS를 수행하며 트리의 모든 정점을 탐색하는 과정에서 '단말 노드'에 방문하면 총 깊이 값에 해당 경로의 깊이 값을 더해줍니다.

 

---

 

#3. 코드

/*
    @문제: 트리 자료구조의 각 단말 노드들의 깊이의 총 합이 '홀수'가 되는 경우 성원이가 이긴다.
    @설명
        1. 트리 DP, Bottom-Up : 실패, 자식 노드 개수를 쌓아 올리며 계산하는 작업은 오류가 있다.
        -> 왜? 두 자식 노드를 가진 부모 노드는 DP[P] = 2 가 되지만, 바로 위 조상 노드의 DP[G] = 4가 되어야 하며, 계산 방식이 dp로는 불가능한 방법.
        2. 단순히, 재귀dfs 활용
        3. 꼼꼼히 읽어보지만, 너무 꼬아서 읽지 말자
*/

#include <iostream>
#include <vector>
using namespace std;

#define MAX 500001

int N;
vector<int> tree[MAX];
int totalDepth;

void dfs(int node, int parent, int depth)
{
    bool isLeaf = true;
    for(auto next : tree[node])
    {
        if(next != parent)
        {
            // 재귀 DFS
            dfs(next, node, depth+1);
            // 단말 노드는 parent 노드 외 다른 노드와 연결되어 있지 않다.
            isLeaf = false;
        }
    }
    if(isLeaf)
    {
        totalDepth += depth;
    }
}

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

    cin >> N;

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

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

    dfs(1, 0, 0);

    totalDepth%2 == 1? cout << "Yes" : cout << "No";

    return 0;
}

 

---