LCA

백준 3176번 도로 네트워크 문제풀이

[3176 도로 네트워크] https://www.acmicpc.net/problem/3176 .
LCA를 구하고 그 때 Sparse table을 이용해보자!

구간 최대, 최소를 구할 때 놀랍게도 전처리를 해두면 O(1)에 구할 수 있는 방법이 있다.
그것이 바로 sparse table이고 최대, 최소는 겹치는 구간이 있어도 상관없기 때문에 겹치는 구간 2개를 이용하는 것이다.

문제상황 파악하기.

도시와 도로가 트리형태로 주어져있고 한 도시에서 다른 도시로 가는 쿼리가 주어지면 경로 상의 가장 짧은 도로와 가장 긴 도로를 출력하면 된다.
K가 최대 10만이므로 최대 O(N(logN)^2))정도에 해결할 수 있다.
한 도시에서 다른 도시로 간다고 하면 둘의 최소 공통 조상을 무조건 지나기 때문에 LCA를 이용할 수 있다.

LCA가 뭐길래

lowest common ancester(최소 공통 조상)이다.
제일 가까운 부모라는 것이다.
구하는 방법은 간단하다. 만날 때까지 위로 올리면 된다.

u, v의 깊이가 다르면 깊은 것을 올린다.
깊이가 같아지면 u==v가 될때까지 동시에 올린다.

위 논리를 이용한 것이 아래 코드이다.

int LCA(int u, int v){
    if(depth[u]<depth[v]) swap(u, v);       //u가 더 깊은거라고 하자
    int diff = depth[u]-depth[v];
    for(int i=0;i<20;i++) if(diff&(1<<i)) u = P[i][u];      //차이 만큼 올라간다.(1번 과정)
    if(u==v) return u;
    for(int i=19;i>=0;i--) if(P[i][u]!=P[i][v]){        //같아질 떄까지 u, v를 동시에 옮긴다.      
        u = P[i][u];
        v = P[i][v];
    }
    return P[0][u];     //같아진것을 리턴한다.      
}

아이디어 얻기.

일단 두 정점사이 길이 하나밖에 없고 LCA는 무조건 지난다.
따라서 sparse table로 최대 최소를 미리 전처리 해두면 LCA를 구하는 과정에서 최대 최소를 구할 수 있을 것이다.
sparse table은 3개를 만들것이고 다음과 같이 정의한다.

P[j][i] : i번 정점에서 2^j 위의 조상
N[j][i] : i번 정점에서 2^j 위의 조상까지 갈 동안 최솟값
X[j][i] : i번 정점에서 2^j 위의 조상까지 갈 동안 최댓값

주의할 점

위의 코드로 LCA를 구하면 최종적으로 u, v가 같은 상태일때가 아니라 LCA바로 이전 정점들이 된다.
따라서 마지막에 리턴전에 최대, 최소를 한번 더 갱신해 줘야한다.

실제 코드

나머지 주의 할 점은 코드에 주석으로 처리했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 987654321;
const int MAX = 100001;
int n, k;
int P[20][MAX], N[20][MAX], X[20][MAX], depth[MAX];
vector<pii> adj[MAX];

void dfs(int here, int parent, int d){
    depth[here] = d;
    P[0][here] = parent;
    for(pii next : adj[here]){
        if(next.first==parent) continue;
        N[0][next.first] = next.second;
        X[0][next.first] = next.second;
        dfs(next.first, here, d+1);
    }
}

pii LCA(int u, int v){
    pii ret;
    ret.first = INF;
    ret.second = 0;
    if(depth[u]<depth[v]) swap(u, v);
    int diff = depth[u]-depth[v];
    for(int i=0;i<20;i++) if(diff&(1<<i)){  // 깊이를 맞추는 과정
        ret.first = min(ret.first, N[i][u]);
        ret.second = max(ret.second, X[i][u]);
        u = P[i][u];
    }
        
    if(u==v){
        return ret;
    }
    for(int i=19;i>=0;i--) if(P[i][u]!=P[i][v]){    // 거슬러 올라가는 과정
        ret.first = min(ret.first, N[i][u]);
        ret.second = max(ret.second, X[i][u]);
        u = P[i][u];
        ret.first = min(ret.first, N[i][v]);
        ret.second = max(ret.second, X[i][v]);
        v = P[i][v];
    }
    //마지막에 갱신을 하고 리턴해야함
    ret.first = min(ret.first, N[0][u]);
    ret.second = max(ret.second, X[0][u]);
    ret.first = min(ret.first, N[0][v]);
    ret.second = max(ret.second, X[0][v]);
    return ret;
}

int main(){
    fast_io
    cin >> n;
    for(int i=1;i<n;i++){
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    dfs(1, 1, 1);
    
    N[0][1] = INF;
    for(int j=1;j<20;j++){          //전처리 과정 O(NlogN)
        for(int i=1;i<=n;i++){
            P[j][i] = P[j-1][P[j-1][i]];
            N[j][i] = min(N[j-1][i], N[j-1][P[j-1][i]]);
            X[j][i] = max(X[j-1][i], X[j-1][P[j-1][i]]);
        }
    }
    
    cin >> k;
    for(int i=0;i<k;i++){       //O(KlogN)
        int u, v; cin >>  u >> v;
        pii res = LCA(u, v);
        cout << res.first << ' ' << res.second << '\n';
    }
}

LCA

백준 3176번 도로 네트워크 문제풀이

문제상황 파악하기.

LCA가 뭐길래

아이디어 얻기.

주의할 점

실제 코드

Leave a comment

2024

2023

2022