[JAVA] 최소 공통 조상 (Lowest Common Ancestor) 구현하기

1. 최소 공통 조상 : 트리에서 두 노드가 있을 때(u와 v), 둘 다의 노드 중에서 가장 가까운(깊은) 노드를 의미한다

-> 공통 부모들 중에서 가장 아래에 있는 노드 

최소 공통 조상

 

 

구현 방법에는 "단순 구현(단순 상승)", "LCA  + DP", "LCA + 세그먼트 트리" 이렇게 3방법이 있다.

이 글에서는 단순 상승을 먼저 다뤄볼 예정이다..!

 

2. 구현 방법 ( 단순 상승 ) 

• BFS(/DFS)탐색을 하면서 각 노드의 부모노드와 깊이를 계산
• 두 노드의 깊이를 비교하여 더 깊은 노드를 올려 두 노드의 깊이를 동일하게 맞춘다
• 두 노드를 동시에 한 칸씩 올리면서 두 노드가 동일해질 때까지 비교한다.

 

3. 구현 코드

package org.bibisam06.tree.template;
/*
    단순 상승 LCA(Lowest Common Ancestor) 구현하기 - Java
*/
import java.util.*;
public class LowestCommonAncestor {

    static int[] parent, depth;
    static ArrayList<Integer>[] graph;

    static void bfs(int root){ // depth, parent 계산
        Arrays.fill(parent, -1);
        Arrays.fill(depth, -1); 
        Queue<Integer> queue = new ArrayDeque<>();

        queue.add(root);
        parent[root] = 0;
        depth[root] = 0;

        while(!queue.isEmpty()) {
            int current = queue.poll();
            List<Integer> nexts = graph[current];

            for(int value : nexts) {
                if(parent[value] != -1) continue;
                parent[value] = current;
                depth[value] = depth[current] + 1;
                queue.add(value);
            }
        }

    }

    /*
        두 노드의 깊이를 비교해 들어올리기(lca)
    */

    static int lca(int a, int b){

        if(depth[a] < depth[b]){
            int t = a;
            a = b;
            b = t; // a가 더 낮은 위치를 가지게 끔 두 노드를 바꿔줌
        }

        while(depth[a] > depth[b]) {
            a = parent[a];
        }// a가 부모 타고 올라감 -> b 랑 높이 맞춰줌

        while(a!=b) {
            a = parent[a];
            b = parent[b];
        }

        return a;
    }

    static void addEdge(int a, int b){
        graph[a].add(b);
        graph[b].add(a);
    }
    public static void main(String[] args){
        // ===== 1) 예시 트리 구성 (노드 1~7) =====
        int N = 7;
        graph  = new ArrayList[N + 1];
        parent = new int[N + 1];
        depth  = new int[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();

        // 예시 트리 (완전이진트리)
        //      1
        //    /   \
        //   2     3
        //  / \   / \
        // 4   5 6   7
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(3, 6);
        addEdge(3, 7);


        int nodeA = 5;
        int nodeB = 3;

        bfs(1);//1번부터 깊이, 부모 저장

        int lcaResult = lca(nodeA, nodeB);

        System.out.println("두 노드의 공통 조상 노드는 " + lcaResult + "입니다.");

    }
}

 

4. 참고 자료 

https://0bliviat3.tistory.com/79

[자료구조] 희소 배열 (Sparse Table)의 구현(JAVA)

https://loosie.tistory.com/364#일반적인_LCA_풀이방법

[알고리즘] 최소 공통 조상 LCA 트리 - DP & 세그먼트 트리 (Java)

 

풀이 깃 주소 : 
https://github.com/bibisam06/data-structures.git

GitHub - bibisam06/data-structures

 

 

5. 예제 문제와 다른 방식 풀이 -> 앞으로 풀면서 추가예정입니다.