BOJ 1761 - 정점들의 거리

www.acmicpc.net/problem/1761

1761번: 정점들의 거리

 

이 문제를 풀기 위해서는 먼저 LCA (Lowest Common Ancestor) Algorithm 에 대해 알고 있어야 한다.

그리고 LCA 를 알기 위해선, 희소 테이블(Sparse Table) 에 대한 사전지식이 있어야한다.

 

 

참고

- 희소 테이블 : blog.naver.com/kks227/220793361738

희소 테이블(Sparse Table) (수정: 2019-11-16)

- LCA : blog.naver.com/kks227/220820773477

최소 공통 조상(Lowest Common Ancestor) (수정: 2019-08-31)

 

 

이 문제는 LCA 에 추가적으로 노드간 거리를 찾기 위해서, 거리 정보를 담고있는 별도의 메모리가 필요하다.

아래 코드에서 int dist[MAX_N] 이라는 배열을 하나 선언하였으며 (dist[i] : 루트노드로 부터 노드 i 번째 까지의 거리)

트리를 만들기 위해 재귀함수를 돌릴때마다, 루트 노드로 부터 자기 자신의 노드 까지의 거리를 갱신하는 방식으로 함수를 돌려준다.

 

예제 입력 1을 기준으로 그래프를 그려보면..

dist 배열을 완성하기 전의 노드간 거리를 나타낸 그래프이고,

재귀함수를 돌면서, dist 배열을 완성하면, 

다음과 같이 길이가 갱신된다.

이 값을 가지고 두 노드간의 거리를 구하기 위해서는 

정점 u 와 LCA 인 노드간 거리 + 정점 v 와 LCA 인 노드간 거리 를 구하면 된다.

 

위 그래프에서 정점 2 와 정점 3 간의 거리를 구한다하면, LCA 가 1 이므로

정점 2 와 LCA 간 거리는 dist[2] - dist[LCA] = 23 - 0

정점 3 과 LCA 간 거리는 dist[3] - dist[LCA] = 22 - 0

dist[2] + dist[3] - 2 * dist[LCA] = 45 가 된다.

 

 

- c++

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
 
#define MAX_N 40001
#define MAX 17  // 반올림 log(2, 40000)
 
using namespace std;
 
int n, m;
int dist[MAX_N];                    // 루트노드로 부터의 거리
int parent[MAX_N][MAX];             // parent[i][k] : i의 2^k 번째 부모
int depth[MAX_N];                   // 트리에서의 깊이
vector<pair<int, int>> adj[MAX_N];  // adj[i].first = i 와 연결된 노드 번호가 first, adj[i].second = i 와 first 간 거리
 
void make_tree(int cur, int distance) {  // 현재 노드, 루트 ~ 현재노드 까지의 거리
    for (int i = 0; i < adj[cur].size(); ++i) {
        int next = adj[cur][i].first;
        int temp = distance;
        if (depth[next] == -1) {
            temp += adj[cur][i].second;
            dist[next] += temp;
            parent[next][0] = cur;
            depth[next] = depth[cur] + 1;
            make_tree(next, temp);
        }
    }
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v, distance;
        cin >> u >> v >> distance;
        u--;
        v--;  // 편의상 인덱스 맞추기위해 감소 시켜서 넣음
        adj[u].push_back({v, distance});
        adj[v].push_back({u, distance});
    }
 
    memset(parent, -1, sizeof(parent));
    fill(depth, depth + n, -1);
    depth[0] = 0;
    make_tree(0, 0);
 
    for (int j = 0; j < MAX - 1; ++j)
        for (int i = 1; i < n; ++i)
            if (parent[i][j] != -1)
                parent[i][j + 1] = parent[parent[i][j]][j];
 
    cin >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, temp_u, temp_v;
        cin >> u >> v;
        u--;
        v--;
 
        temp_u = u;
        temp_v = v;
 
        if (depth[u] < depth[v]) swap(u, v);
 
        int diff = depth[u] - depth[v];
 
        for (int j = 0; diff; ++j) {
            if (diff % 2) u = parent[u][j];
            diff /= 2;
        }
 
        if (u != v) {
            for (int j = MAX - 1; j >= 0; --j) {
                if (parent[u][j] != -1 && parent[u][j] != parent[v][j]) {
                    u = parent[u][j];
                    v = parent[v][j];
                }
            }
            u = parent[u][0];
        }
 
        cout << dist[temp_u] + dist[temp_v] - (2 * dist[u]) << "\n";
    }
 
    return 0;
}