[백준] 3176: 도로 네트워크

0. 문제 주소

 

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

3176번: 도로 네트워크

 

 

1. 풀이

 

N이 10만, 쿼리 개수가 10만이라 한 쿼리당 log N이 걸려야 한다.

 

[PS/LCA] - [BOJ] 1626: 두 번째로 작은 스패닝 트리에서 했던 것처럼, sparse table을 하나 더 만들어서

 

dist[i][j] = i번 노드에서 2^j번째 부모 사이의 간선 중 pair ( 가중치가 가장 작은 값, 가장 큰 값 )으로 저장해준다.

 

자세한 풀이는 아래와 같다.

 

 

0. depth, parent 배열은 -1로 초기화해준다. dist 배열은 최소, 최대 비교에 지장이 없게 pair ( INF, 0 )으로 초기화해준다.

 

1. DFS를 이용해 트리를 만들어 준다. 루트 노드의 depth를 0으로 초기화해두고, 방문하지 않은 인접한 노드들에 대해

  depth[next] = depth[curr] + 1, parent[next][0] = curr로 설정해주고, next를 이어서 탐색하면 된다.

 

2. 이 문제에서는 curr와 next 사이의 간선의 가중치를 d라고 했을 때, dist[next][0] = pair( d, d )로 설정해준다.

 

3. 다음 sparse table의 나머지 부분들을 채워준다.

 

for (int j=0;j<P_MAX-1;j++){
    for (int i=2;i<=N;i++){
        if (parent[i][j] != -1){
            parent[i][j+1] = parent[parent[i][j]][j];
            dist[i][j+1] = pii( min(dist[i][j].first, dist[parent[i][j]][j].first), max(dist[i][j].second, dist[parent[i][j]][j].second) );
        }
    }
}

 

4. 쿼리 u, v를 받으면, 기존과 동일하게 LCA를 찾는다.

   4-1. u의 depth를 더 깊게 만들어 준다.

   4-2. u와 v의 depth를 같게 만들어 준다 : depth 차이인 diff를 2진수로 표현하여 u를 올린다.

   4-3. u와 v가 같지 않으면, (LCA와 u, v 사이의 거리 - 1)을 2진수로 분해해 올린다.

   4-4. 마지막으로 한 번 더 올려 준다. 

   4-5. 4의 과정 중에서, 거쳐갔던 모든 dist 값들 중 최솟값, 최댓값을 실시간으로 갱신해 준다.

 

for (int i=0;i<M;i++){
    int u, v;
    scanf("%d %d", &u, &v);
    
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    int curr_max = 0, curr_min = INF;
    
    for (int j=0;diff;j++){
        if (diff%2) {
            curr_min = min(curr_min, dist[u][j].first);
            curr_max = max(curr_max, dist[u][j].second);
            u = parent[u][j];
        }
        diff /= 2;
    }
    
    if (u != v){
        for (int j=P_MAX-1;j>=0;j--){
            if (parent[u][j] != -1 && parent[u][j] != parent[v][j]){
                curr_min = min(curr_min, dist[u][j].first);
                curr_max = max(curr_max, dist[u][j].second);
                u = parent[u][j];
                curr_min = min(curr_min, dist[v][j].first);
                curr_max = max(curr_max, dist[v][j].second);
                v = parent[v][j];
            }
        }
        curr_min = min(curr_min, min(dist[u][0].first, dist[v][0].first));
        curr_max = max(curr_max, max(dist[u][0].second, dist[v][0].second));
        u = parent[u][0];
    }
    
    printf("%d %d\n", curr_min, curr_max);
    
    
}

 

5. 4-5.에서 찾은 최솟값, 최댓값이 답이 된다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>

#define NODE_MAX 100005
#define P_MAX 18
#define INF 987654321
#define pii pair<int, int>

using namespace std;

int N, M;
int parent[NODE_MAX][P_MAX];
int depth[NODE_MAX];
pii dist[NODE_MAX][P_MAX]; // dist[i][j] = pair ( i번 노드 ~ i번 노드의 2^j번째 노드 까지의 최솟값과 최댓값) 
vector<pii> graph[NODE_MAX];

void maketree(int curr){
    for (auto p: graph[curr]){
        int next = p.first;
        int weight = p.second;
        if (depth[next] == -1){
            parent[next][0] = curr;
            depth[next] = depth[curr] + 1;
            dist[next][0] = pii(weight, weight);
            maketree(next);
        }
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d", &N);
    for (int i=0;i<N-1;i++){
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        graph[u].push_back(pii(v, c));
        graph[v].push_back(pii(u, c));
    }
    
    memset(parent, -1, sizeof(parent));
    memset(depth, -1, sizeof(depth));
    for (int i=1;i<=N;i++){
        for (int j=0;j<P_MAX;j++){
            dist[i][j] = pii(INF, 0);
        }
    }
    
    depth[1] = 0;
    maketree(1);
    
    for (int j=0;j<P_MAX-1;j++){
        for (int i=2;i<=N;i++){
            if (parent[i][j] != -1){
                parent[i][j+1] = parent[parent[i][j]][j];
                dist[i][j+1] = pii( min(dist[i][j].first, dist[parent[i][j]][j].first), max(dist[i][j].second, dist[parent[i][j]][j].second) );
            }
        }
    }

    
    scanf("%d", &M);
    for (int i=0;i<M;i++){
        int u, v;
        scanf("%d %d", &u, &v);
        
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        int curr_max = 0, curr_min = INF;
        
        for (int j=0;diff;j++){
            if (diff%2) {
                curr_min = min(curr_min, dist[u][j].first);
                curr_max = max(curr_max, dist[u][j].second);
                u = parent[u][j];
            }
            diff /= 2;
        }
        
        if (u != v){
            for (int j=P_MAX-1;j>=0;j--){
                if (parent[u][j] != -1 && parent[u][j] != parent[v][j]){
                    curr_min = min(curr_min, dist[u][j].first);
                    curr_max = max(curr_max, dist[u][j].second);
                    u = parent[u][j];
                    curr_min = min(curr_min, dist[v][j].first);
                    curr_max = max(curr_max, dist[v][j].second);
                    v = parent[v][j];
                }
            }
            curr_min = min(curr_min, min(dist[u][0].first, dist[v][0].first));
            curr_max = max(curr_max, max(dist[u][0].second, dist[v][0].second));
            u = parent[u][0];
        }
        
        printf("%d %d\n", curr_min, curr_max);
        
        
    }
    
}