LCA(Lowest Common Ancestor) 알고리즘

LCA(Lowest Common Ancestor) 알고리즘 

AKA. 최소 공통 조상 알고리즘

 

• 요약 : 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘이다.

출처 : 동빈나 최소 공통 조상(Lowest Common Ancestor, LCA) 알고리즘 10분 정복

• 구현법 : 일반적으로 DFS를 활용해 구현한다. 다이나믹 프로그래밍(DP), 세그먼트 트리를 활용해 시간 복잡도를 개선할 수 있다. 
  (1) 모든 노드에 대한 깊이(depth)를 계산한다. 
  (2) 최소 공통 조상을 찾을 두 노드를 확인한다. 
      (2)-(1) 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다. = 같은 라인에 위치할때까지 올라간다.
      (2)-(2) 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. 
  (3) 모든 LCA(a,b) 연산에 대하여 2번의 과정을 반복한다. 
  
  
• 기본 구현 코드

//문제 예시 : https://www.acmicpc.net/problem/11437
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 50000
using namespace std;

vector<vector<int>> v;
int parent[MAX] = {};
int level[MAX] = {};
bool check[MAX];

void balancing(int &n1, int &n2){
    while(level[n1]>level[n2]) n1 = parent[n1];
    while(level[n1]<level[n2]) n2 = parent[n2];
}

void setParentLevel(int n){
    check[n] = true;
    int edgeCount = v[n].size();
    for(int i=0; i<edgeCount; i++){
        int vert = v[n][i];
        if(!check[vert]){
            parent[vert] = n;
            level[vert] = level[n] + 1;
            setParentLevel(vert);
        }
    }
}

int main(void) {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int n=0, m=0;
   cin >> n;
   v.resize(n+1);
   for(int i=0; i<n-1; i++){
       int to=0, des=0;
       cin >> to >> des;
       v[to].push_back(des);
       v[des].push_back(to);
   }
   setParentLevel(0);
   cin >> m;
   for(int i=0; i<m; i++){
       int n1=0, n2=0;
       cin >> n1 >> n2;
       balancing(n1,n2);
       while(n1!=n2){
           n1 = parent[n1];
           n2 = parent[n2];
       }
       cout << n1 << "\n";
   }
   return 0;
}

알고리즘 참조 출처 : girlfriend-yerin.tistory.com/127

Baekjoon 11437 LCA

• 시간복잡도 : O(NM) 
  매 쿼리마다 부모 방향으로 거슬러 올라가기 위해 최악의 경우 O(N)의 시간 복잡도가 요구됨
  따라서 모든 쿼리를 처리할 때 시간 복잡도는 O(NM)