[BOJ알고리즘, C++]#1761_정점들의 거리, LCA, LCA 최단/최장 거리 찾기

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. LCA 알고리즘

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

LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가장 깊은 곳에 위치한 공통 조상 노드를 의미합니다. LCA 알고리즘은 Binary Lifting 기법을 통해 최적화를 수행하며, 두 노드 사이의 공통 조상 노드를 찾는 작업 외에 최장/최단 거리를 찾는 데에도 활용됩니다.

 

2. LCA를 통해 두 노드 사이의 거리 찾기

dist(A, B) = dist(root, A) + dist(root, B) - 2 * (root, LCA)

트리 자료구조에서 LCA를 활용해 두 노드 사이의 거리를 찾는 공식은 위와 같습니다.

 

3. LCA를 통해 공통 조상 노드를 찾고, 이를 활용해 거리를 찾는다!

1. 먼저, LCA 알고리즘을 수행하기 위해 DFS를 통해 트리 자료구조의 각 정점의 부모 목록과 깊이 목록을 초기화합니다.
2. LCA를 수행하여, 두 노드의 가장 가까운 공통 조상 노드를 찾습니다.
3. "dist(A, B) = dist(root, A) + dist(root, B) - 2 * (root, LCA)" 공식을 활용해 두 노드 사이의 거리를 찾아 출력합니다.

 

---

 

#3. 코드

 

/*
    문제 : 두 노드 쌍의 거리 구하기
    설명
            1. LCA 알고리즘 활용 : dfs를 통해 조상 노드 목록과 깊이 목록 초기화, LCA를 통한 가장 가까운 공통 조상 찾기
            2. dist(A, B) = dist(root, A) + dist(root, B) - 2 * (root, LCA)
*/

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

#define MAX 40001
#define LOG 16

int anc[MAX][LOG];
int depth[MAX], dist[MAX];
vector<pair<int,int>> tree[MAX];

int N, M;

// #1. DFS를 활용하여 조상 노드, 깊이 목록, 거리 값 목록 초기화
void dfs(int cur, int parent, int distance)
{
    // [0]은 2^0 = 1 위 조상 노드(직속 부모 노드)
    anc[cur][0] = parent;
    // 거리 값 초기화
    dist[cur] = distance;
    // 조상 노드 목록 초기화
    for(int i=1; i<LOG; ++i)
    {
        anc[cur][i] = anc[anc[cur][i-1]][i-1];
    }
    for(const auto p : tree[cur])
    {
        if(p.first == parent) continue;

        depth[p.first] = depth[cur]+1;
        dfs(p.first, cur, dist[cur]+p.second);
    }
}

int lca(int u, int v)
{
    // #1. u를 v보다 항상 큰 깊이 값을 갖는 노드로 변경
    if(depth[u] < depth[v]) swap(u,v);
    // #2. u와 v의 깊이를 맞춰줍니다.
    for(int i=LOG-1; i>=0; --i)
    {
        if(depth[u] - (1<<i) >= depth[v]) u = anc[u][i];
    }
    // #3. 같은 노드라면 그냥 u 반환
    if(u==v) return u;
    // #4. 공통 조상 찾기
    for(int i = LOG-1; i >= 0; --i)
    {
        if(anc[u][i] != anc[v][i])
        {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}

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 u, v, dist;
        cin >> u >> v >> dist;

        tree[u].push_back({v, dist});
        tree[v].push_back({u, dist});
    }

    // #1. 임의의 루트 노드 '1'번을 시작으로 하는 DFS 호출
    dfs(1, -1, 0);

    cin >> M;
    while(M--)
    {
        int u, v;
        cin >> u >> v;

        int LCA = lca(u,v);
        // #2. dist(A, B) = dist(root, A) + dist(root, B) - 2 * dist(root, lca(A, B))
        cout << dist[u] + dist[v] - 2 * dist[LCA] << '\n';
    }

    return 0;
}

 

---