[BOJ알고리즘, C++]#3176_도로 네트워크, 트리, LCA, LCA 최단/최장 거리 찾기

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. LCA

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

LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. LCA 알고리즘은 Binary Lifting 기법을 활용해 최적화를 수행하며, 일반적으로 두 노드의 공통 조상을 찾거나, 두 노드 사이의 거리 혹은 최단/최대 거리를 찾는데 활용됩니다.

 

2. 질문을 통해 '트리 자료구조'를 확정하고, LCA를 활용하자!

1. 먼저, '트리' 자료구조는 그래프의 한 종류로 계층 구조를 형성하고, 순환 구조가 없는 그래프입니다. 따라서, N개의 노드와 N-1개의 간선으로 이루어지며, 두 노드 사이의 경로는 유일합니다! 따라서, 그래프의 최단/최대 거리를 찾는다기 보다, 트리 자료구조의 두 노드 사이의 최단/최장 거리를 찾는데 더 용이한 LCA 알고리즘을 추론해 볼 수 있습니다.
2. 먼저, DFS를 통해 트리 자료구조의 각 노드에 대한 깊이 목록과 부모 노드 목록을 초기화합니다. 이때, 두 노드 사이의 거리를 찾기 위해 부모 노드 목록 초기화 과정에서 현재 노드와 각 부모 노드(2^j) 사이의 거리가 최소/최대가 되는 값을 찾아줍니다.
3. 그리고, LCA를 활용하여 두 노드 사이의 깊이를 맞추는 작업 + 가장 가까운 부모를 찾는 과정에서 최소/최대 거리 값을 갱신하며, 최종적으로 두 노드의 가장 가까운 공통 조상이 갖는 최소/최대 거리를 찾아서 반환해 줍니다.

 

---

 

#3. 코드

 

/*
    @문제 : 트리 자료구조의 두 노드 쌍의 최단 거리와 최대 거리 구하기
    @설명
            1. LCA 활용 문제 : 트리에서 두 노드 간 거리는 LCA를 활용하자
            2. 두 노드 쌍의 공통 조상을 찾으며, 이와 동시에 최소/최대 거리를 구할 수 있다!
*/

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

#define MAX 100001
#define LOG 17

int depth[MAX], parent[MAX][LOG], minDist[MAX][LOG], maxDist[MAX][LOG];
vector<pair<int,int>> tree[MAX];

int N, K;

void dfs(int cur, int p)
{
    depth[cur] = depth[p]+1;
    parent[cur][0] = p;

    for(int j=1; j<LOG; ++j)
    {
        if(parent[cur][j-1] != -1)
        {
            parent[cur][j] = parent[parent[cur][j-1]][j-1];
            minDist[cur][j] = min(minDist[cur][j-1], minDist[parent[cur][j-1]][j-1]);
            maxDist[cur][j] = max(maxDist[cur][j-1], maxDist[parent[cur][j-1]][j-1]);
        }
        else parent[cur][j] = -1;
    }

    for(const auto edge : tree[cur])
    {
        int next = edge.first;
        int dist = edge.second;

        if(next == p) continue;

        // 깊이, 부모, 최소 거리, 최대 거리
        minDist[next][0] = maxDist[next][0] = dist;
        // 재귀 DFS
        dfs(next, cur);
    }
}

pair<int,int> lca(int u, int v)
{
    int minD = INT_MAX, maxD = INT_MIN;
    // #1. u가 항상 깊은 노드로 설정, u > v
    if(depth[u] < depth[v]) swap(u,v);

    // #2. 두 노드의 깊이, 최소, 최대 거리 맞추기
    for(int k=LOG-1; k>=0; --k)
    {
        if(depth[u] - depth[v] >= (1<<k))
        {
            minD = min(minD, minDist[u][k]);
            maxD = max(maxD, maxDist[u][k]);
            u = parent[u][k];
        }
    }

    // #3. u == v?
    if(u == v) return {minD, maxD};

    // #4. LCA 찾기
    for(int k=LOG-1; k>=0; --k)
    {
        if(parent[u][k] != parent[v][k])
        {
            minD = min(minD, min(minDist[u][k], minDist[v][k]));
            maxD = max(maxD, max(maxDist[u][k], maxDist[v][k]));
            u = parent[u][k];
            v = parent[v][k];
        }
    }

    // #5. 결과 반환
    minD = min(minD, min(minDist[u][0], minDist[v][0]));
    maxD = max(maxD, max(maxDist[u][0], maxDist[v][0]));
    return {minD, maxD};
}

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

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

    dfs(1,0);

    cin >> K;

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

        // 두 노드 쌍의 최대 거리와 최단 거리
        pair<int,int> res = lca(u,v);

        cout << res.first << ' ' << res.second << '\n';
    }

    return 0;
}

 

---