[BOJ알고리즘, C++]#15681_트리와 쿼리, 트리, DFS, DP

 

#1. 문제

15681번: 트리와 쿼리

 

---

 

#2. 풀이

 

1. 트리

[자료구조]#5_트리

 

트리는 1:N 관계의 계층 구조를 갖는 비 선형 자료구조입니다. 트리는 노드와 간선으로 구성되며, 노드 간 연결 관계를 간선으로 나타냅니다. 트리는 계층구조를 갖는 동시에, 비순환 구조를 갖습니다.

 

2. DFS, 깊이 우선 탐색

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

 

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. DFS는 그래프의 출발 정점으로부터 더 이상 확장 할 수 없는 단말 노드까지 우선적으로 탐색을 진행하고, 최종적으로 모든 정점을 탐색합니다. 일반적으로, DFS는 재귀 호출 혹은 스택 자료구조를 활용하여 구현 가능합니다.

 

3. DP, 동적 계획법

[알고리즘]#5_동적 계획법

 

동적 계획법은 최적화 기법 중 하나입니다. 동적 계획법은 주어진 입력 크기에 따라 하위 문제들을 재귀적으로 해결하고, 그 결과 값을 기억합니다. 이를 통해, 중복 계산을 피해 최적화를 수행하고, 효율적으로 최적 해를 찾습니다. 

 

4. 트리 - DFS - DP, 3위 일체

 

1. 전형적인 트리 - DFS - DP 삼위일체 문제입니다.
2. 트리를 구성하고, 재귀 호출을 수행하는 DFS를 통해 현재 레벨의 마지막 단말 노드에 다다르면, 그 결과 값을 기억하고 다시 반환하며 DP를 수행하는 전형적인 문제입니다.
3. DFS를 수행하며, 각 노드는 자식 노드들을 순회하며 이들이 기억해 놓은 DP 값들을 모두 가져와 자신의 DP값에 더해주는 것으로 해당 문제를 쉽게 해결할 수 있습니다.

 

---

 

#3. 코드

 

/*
    @문제 : 각 정점을 루트 노드로 하는 서브트리의 모든 정점의 개수
    @설명
            1. 루트 노드를 시작으로 DFS를 수행
            2. 이때, 현재 노드를 루트 노드로하는 서브트리의 정점 개수를 재귀적으로 계산
            3. Bottom-Up 형식으로 각 정점을 루트 노드로 하는 서브트리의 개수를 찾는다.
*/

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

int N, R, Q;
vector<vector<int>> tree;
vector<int> subTree;

int dfs(int cur, int parent)
{
    subTree[cur] = 1;

    for (const auto &neighbor : tree[cur])
    {
        if (neighbor != parent)
        {
            subTree[cur] += dfs(neighbor, cur);
        }
    }

    return subTree[cur];
}

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

    cin >> N >> R >> Q;

    tree.resize(N + 1);
    subTree.resize(N + 1, 0);

    // #1. 트리 구성
    for (int i = 0; i < N - 1; ++i)
    {
        int u, v;
        cin >> u >> v;

        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // #2. 루트 노드를 시작으로 DFS 수행하며, 각 정점이 루트 노드가 되는 서브트리의 모든 정점의 개수 세기
    dfs(R, -1);

    while (Q--)
    {
        int root;

        cin >> root;

        cout << subTree[root] << '\n';
    }

    return 0;
}

 

---