LCA (최소공통조상)

LCA는 Lowest Common Ancestor의 약자로 최소 공통 조상을 찾는 알고리즘이다. 

트리구조에서 사용되며 두 정점 u, v에서 가장 가까운 공통 조상을 찾으면 된다. 

 

 

 

 

 

이 그래프에서 13번 정점과 15번 정점의 최소공통조상은 5번 정점이다.

 

 

 

 

 

 

 

11번 정점과 13번 정점의 최소공통조상은 1번 정점이다.

 

 

 

 

 

 

 

이런 상황에서 12번 정점과 14번 정점의 최소공통조상은 12번 정점이다.

 

 

 

 

🕹️ LCA 과정 

1️⃣ 입력받은 정점과 간선으로 양방향 그래프 (트리구조) 를 생성한다. 

2️⃣ BFS나 DFS를 사용하여 depth를, DP를 활용하여 parent 정보를 저장하는 트리를 생성한다.

3️⃣ LCA(u, v) 메서드를 호출하여 u와 v의 최소공통조상을 찾는다. 

1. u와 v 중에서 깊이가 더 깊은 정점을 얕은 깊이의 정점까지 거슬러 올라간다. (깊이 동일하게 만들어주기)
2. 정점의 부모를 따라 같이 하나씩 올라가서 LCA를 찾는다. 

➡️ 이 방법으로 진행할 시 트리 깊이가 그다지 깊지 않으면 괜찮으나, 깊이가 깊어질수록 시간복잡도가 상당히 커진다. 

 

⏳ 시간복잡도 : O(H) (트리의 깊이 = H, 최악의 경우 O(N))

---

👉 위의 문제점을 해결하는 방법은 각 노드가 거슬러 올라가는 속도를 빠르게 만들어 주는 것이다. 

만약, 15칸을 이동한다면 8칸 → 4칸 → 2칸 → 1칸 이런식으로 이동할 시 보다 빠르게 LCA를 구할 수 있다. 

즉, 2의 제곱의 형태로 거슬러 올라가면 O(logN)의 시간복잡도를 가지게 된다.  

 

 

 

LCA  코드 구현

 

1️⃣ 입력받은 정점과 간선으로 양방향 그래프를 생성하는 코드

static ArrayList<Integer>[] tree;

public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
        n = Integer.parseInt(br.readLine());
        
   		// 그래프 생성 및 초기화 
        tree = new ArrayList[n+1];

        for(int i=0; i<=n; i++){
            tree[i] = new ArrayList<>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=1; i<n; i++){
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree[a].add(b); // 트리 정보 저장 → 노드 연결
            tree[b].add(a);

        }
}

 

2️⃣ BFS나 DFS를 이용하여 깊이 정보 저장 

static int[] depth;
static int[][] parent;

// BFS
static void bfs(int start) {
    ArrayDeque<Integer> dq = new ArrayDeque<>();
    depth[start] = 1;
    dq.add(start);

    while (!dq.isEmpty()) {
        int now = dq.poll();
        for (int next : tree[now]) {
            if (depth[next] == 0) {
                depth[next] = depth[now]+1;
                parent[0][next] = now; // 해당 노드 바로 위에 있는 부모 저장. (next 깊이 = now 깊이 + 1) next의 부모 = now
                dq.add(next);
            }
        }
    }
}

// DFS
static void dfs(int node, int cnt) {

    // 1. depth 기록
    depth[node]= cnt;

    // 2. 자식들의 depth 기록
    int len= tree[node].size(); // 자식 개수
    for(int i=0; i<len; i++) {
        int next= (Integer)tree[node].get(i);
        //아직 깊이를 모르면 → 미방문 노드
        if(depth[next]==0) {
            dfs(next, cnt+1);
            parent[0][next]= node; //next 노드의 2^0 = 첫번째 부모 기록 → 해당 노드 바로 위에 있는 부모 저장
        }
    }
}

 

3️⃣ DP를 활용하여 부모 채우기

parent[K][V] = parent[K-1][parent[K-1][V]]   ➡️ 정점 V의 2^K번째 조상 정점 번호

static void getSparseTable(){
    for(int i=1; i<=logN; i++){
        for(int j=1; j<=n; j++){
            parent[i][j] = parent[i-1][parent[i-1][j]];
        }
    }
}

ex)

1, 2, 4는 2^0, 2^1, 2^2의 값이다. i의 값이 2의 지수 쪽을 의미한다. (i=0, 1, 2, .... 17)

parent[2][1] = parent[1][0] = 0  ➔ 노드 1에서 2만큼 올라간 노드의 값 = 0

parent[2][2] = parent[1][1] = 0  ➔ 노드 2에서 2만큼 올라간 노드의 값 = 0

parent[2][3] = parent[1][1] = 0 ➔ 노드 3에서 2만큼 올라간 노드의 값 = 0

parent[2][4] = parent[1][2] = 1 ➔ 노드 4에서 2만큼 올라간 노드의 값 = 1 

parent[2][8] = parent[1][3] = 1 ➔ 노드 8에서 2만큼 올라간 노드의 값 = 1 

parent[2][15] = parent[1][11] = 1 ➔ 노드 15에서 2만큼 올라간 노드의 값 = 5

 

4️⃣ LCA 찾기

static int getLCA(int a, int b) {

        if (depth[a] < depth[b]) {
            return getLCA(b,a);
        }

        // 높이 맞추기
        for(int i=0; i<=logN; i++){
            if(((depth[a]-depth[b]) & (1<<i)) >=1){ // 비트 AND 연산 => 둘다 1일 경우 1로 반환
                a = parent[i][a];
            }
        }

        // 높이 맞추기 -> 다른 방법
        /*for(int i=logN; i>=0; i--){
            if(Math.pow(2,i)<=depth[a]-depth[b])){
                a = parent[i][a];
            }
        }*/

        // 높이 맞췄으면 같은지 검사
        if(a==b){
            return a;
        }

        // 공통조상이 아닐 때까지 부모를 따라 올라감
        // 최종적으로는 LCA 바로 밑칸까지만 올라감.
        for(int i=logN; i>=0; i--){
            if (parent[i][a] != parent[i][b]) {
                a = parent[i][a];
                b = parent[i][b];
            }
        }
        return parent[0][a];
    }

 

/**
 * 11438_LCA 2
 * sparse table 최소 공통조상 빠르게 구하기
 * N의 크기 = 10만
 * M의 크기 = 10만  => 2^17=약 13만 => sparseTable 사용
 */
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ_11438_LCA2 {

    static int n,m;
    static int logN = 17; // K => 2의 몇 제곱까지 계산할지 저장한 변수 => 17로 선언해도 무방
    static ArrayList<Integer>[] tree;
    static int[] depth;
    static boolean[] visited;
    static int[][] parent; // sparse table


    static void bfs(int start) {
        ArrayDeque<Integer> dq = new ArrayDeque<>();
        depth[start] = 1;
        dq.add(start);

        while (!dq.isEmpty()) {
            int now = dq.poll();
            for (int next : tree[now]) {
                if (depth[next] == 0) {
                    depth[next] = depth[now]+1;
                    parent[0][next] = now;
                    dq.add(next);
                }
            }
        }
    }

    static void getSparseTable(){
        for(int i=1; i<=logN; i++){
            for(int j=1; j<=n; j++){
                parent[i][j] = parent[i-1][parent[i-1][j]];
            }
        }
    }


    static int getLCA(int a, int b) {
        if (depth[a] < depth[b]) {
            return getLCA(b,a);
        }

        // 높이 맞추기
        for(int i=0; i<=logN; i++){
            if(((depth[a]-depth[b]) & (1<<i)) >=1){ // 비트 AND 연산 => 둘다 1일 경우 1로 반환
                a = parent[i][a];
            }
        }

        // 높이 맞추기 -> 다른 방법
        /*for(int i=logN; i>=0; i--){
            if(Math.pow(2,i)<=(depth[a]-depth[b])){
                a = parent[i][a];
            }
        }*/

        // 높이 맞췄으면 같은지 검사
        if(a==b){
            return a;
        }

        // 공통조상이 아닐 때까지 부모를 따라 올라감
        // 최종적으로는 LCA 바로 밑칸까지만 올라감.
        for(int i=logN; i>=0; i--){
            if (parent[i][a] != parent[i][b]) {
                a = parent[i][a];
                b = parent[i][b];
            }
        }
        return parent[0][a];
    }



    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());
        
        tree = new ArrayList[n+1];
        visited = new boolean[n + 1];
        depth = new int[n + 1];
        parent = new int[logN + 1][n+1]; // 시간복잡도상 첫번째 배열에 적은 수 넣는 것이 더 효율적

        for(int i=0; i<=n; i++){
            tree[i] = new ArrayList<>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=1; i<n; i++){
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree[a].add(b);
            tree[b].add(a);

        }

        bfs(1);
        getSparseTable();

        m= Integer.parseInt(br.readLine());

        for(int i=1; i<=m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            bw.write(getLCA(a, b) + "\n");
        }
        bw.flush();
        bw.close();
    }
}