[백준,c++] 11438번 - LCA 2

문제

11438번: LCA 2

 

코드

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;

vector<int> graph[100001];
bool visited[100001];
int parent[100001][21];
int depth[100001];
int N, M, max_height;


void dfs(int node, int _depth){ // 노드 깊이 세팅
    visited[node] = 1;
    depth[node] = _depth;
    for(auto next: graph[node]){
        if(visited[next]) continue;
        parent[next][0] = node; // 한 칸 위의 조상 저장
        dfs(next, _depth+1);
    }
}

void parent_set(){  // 전체 부모 세팅
    for(int i=1; i<max_height; i++){   // max height
        for(int k=1; k<=N; k++){
            if(parent[k][i-1] != 0){
                parent[k][i] = parent[parent[k][i-1]][i-1];
            }
        }
    }
}

int lca(int a, int b){
    
    if(depth[a] > depth[b]) swap(a,b);  // b의 노드의 깊이가 더 깊게 만들어준다.
    
    
    for(int i=max_height; i>=0; i--){   // depth가 같도록 세팅
        int diff = depth[b] - depth[a]; // 두 노드의 깊이 차
        if(diff >= (1<<i)) b = parent[b][i];
    }
    
    if(a == b) return a;
    
    for(int i=max_height; i>=0; i--){   // 조상을 향해 거슬러 올라가기
        if(parent[a][i] != parent[b][i]){
            a = parent[a][i];
            b = parent[b][i];
        }
    }
    return parent[a][0];
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    for(int i=0; i<N-1; i++){
        int a, b; cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    int temp = N;
    while(temp>0){
        max_height++;
        temp = temp>>1;
    }
    dfs(1,0);
    parent_set();

    cin>>M;
    for(int i=0; i<M; i++){
        int a, b; cin>>a>>b;
        cout<<lca(a,b)<<'\n';
    }
}

 

풀이

[백준,c++] 11437번 - LCA

이전에 풀었던 위 LCA 1문제에서 정점의 개수가 50,000에서 100,000으로 늘어났고, 두 노드의 쌍 역시 10,000에서 100,000으로 늘어났습니다.

따라서 트리의 높이가 다를 경우 한 단계씩 올라가면서 맞추는 경우는 트리가 깊어질수록 오래 걸리기 때문에 시간 초과가 발생하게 됩니다.

따라서 기존의 풀이 방식에서 조금 더 개선점을 찾아야 하는데 각 노드가 거슬러 올라가는 속도를 빠르게 만드는 방법은 아래와 같습니다.

• 만약 총 15칸 거슬러 올라가야 한다면?
• 8칸 -> 4칸 -> 2칸 -> 1칸
• 2의 제곱 형태로 거슬러 올라가도록 하면 O(logN)의 시간 복잡도를 보장할 수 있습니다.
• 메모리를 조금 더 사용하여 각 노드에 대하여 2^i번째 부모에 대한 정보를 기록합니다.

즉 다이나믹 프로그래밍을 이용해 각 부모의 2^i번째 부모에 대한 정보를 기록하여 시간 복잡도를 개선할 수 있습니다.

매 쿼리마다 부모를 거슬러 올라가기 위해 (logN)의 복잡도가 필요하며, 모든 쿼리를 처리할 때의 시간 복잡도는 O(MlogN)이 됩니다.