[BOJ알고리즘, C++]#3584_가장 가까운 공통 조상, 트리, LCA

 

#1. 문제

3584번: 가장 가까운 공통 조상

 

---

 

#2. 풀이

 

1. 트리

[자료구조]#5_트리

 

트리는 그래프 자료구조의 한 종류로, 1:N 관계의 계층 구조를 갖는 비 선형 자료구조입니다. 트리는 노드와 간선으로 구성되며, 노드 간의 연결관계는 간선을 통해 표현합니다. 트리는 비순환 구조이며, 계층 구조를 형성하는 특징이 있습니다.

 

2. LCA(Least Common Ancestor)

 

[알고리즘]#7_LCA(Least Common Ancestor)

 

LCA(Least Common Ancestor) 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 특히, 루트가 있는 트리에서 두 노드가 주어졌을 때, 이들의 경로 상에서 가장 높은 레벨 혹은 높은 깊이에 위치한 공통 조상을 찾는 것을 의미합니다. * 높은 레벨은 곧 트리의 루트로부터 가장 먼 위치의 노드를 의미합니다.

 

3. LCA는 깊이, 부모!

 

1. 먼저, 주어진 입력을 통해 각 노드의 부모 노드 정보를 기억합니다.
2. 그리고, 부모 노드 정보를 통해 루트 노드를 찾습니다.
3. 루트 노드를 출발점으로 하는 DFS를 수행하며 각 노드의 깊이 정보를 계산합니다.
4. LCA를 수행합니다!

 

---

 

#3. 코드

 

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

int T, N;
vector<int> parent, depth;

void FindDepth(int node, int d) {
    depth[node] = d;
    for (int i = 1; i <= N; ++i) {
        if (parent[i] == node) {
            FindDepth(i, d + 1);
        }
    }
}

int LCA(int u, int v) {
    while (depth[u] != depth[v]) {
        if (depth[u] > depth[v]) {
            u = parent[u];
        } else {
            v = parent[v];
        }
    }

    while (u != v) {
        u = parent[u];
        v = parent[v];
    }

    return u;
}

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

    cin >> T;

    while (T--) {
        cin >> N;

        parent = vector<int>(N + 1, 0);
        depth = vector<int>(N + 1, 0);

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

            parent[v] = u;
        }

        int root;
        for (int i = 1; i <= N; ++i) {
            if (parent[i] == 0) {
                root = i;
                break;
            }
        }

        FindDepth(root, 0);

        int u, v;
        cin >> u >> v;

        cout << LCA(u, v) << '\n';
    }

    return 0;
}

 

---