최소 공통 조상 (LCA)

1. 개요

• LCA 알고리즘은 주어진 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘이다.
• 비순환 그래프에서 두 노드를 연결하는 경로에 공통으로 존재하는 조상 노드 중 가장 가까운 조상을 찾는다.
• 이 알고리즘은 트리 구조에서 데이터의 계층적 관계를 분석할 때 유용하게 사용된다.

---

2. 특징

• 시간 복잡도: O(depth)이며 최악의 경우 O(N)이다.
• N은 원소 개수
• 두 노드의 depth를 맞춘 후, 하나씩 거슬러 올라가며 공통 조상을 찾는다.

---

3. 코드

public class LCATest {
    public static void main(String[] args) {
        // 예제 트리 구성
        // 부모 인덱스 배열 (0번 인덱스는 사용하지 않음)
        int[] parentList = {0, 0, 1, 1, 2, 2, 3, 3}; // 각 노드의 부모 인덱스
        // 노드의 레벨 (깊이) 배열 (0번 인덱스는 사용하지 않음)
        int[] level = {0, 1, 2, 2, 3, 3, 3, 3}; // 각 노드의 레벨
        
        // 트리 예시
        //        1
        //      /   \
        //     2     3
        //    / \   / \
        //   4   5 6   7
        
        // 노드 4와 5의 LCA 찾기
        System.out.println("노드 4와 5의 LCA: " + LCA(parentList, level, 4, 5));
        // 노드 4와 6의 LCA 찾기
        System.out.println("노드 4와 6의 LCA: " + LCA(parentList, level, 4, 6));
        // 노드 3와 4의 LCA 찾기
        System.out.println("노드 3와 4의 LCA: " + LCA(parentList, level, 3, 4));
        // 노드 2와 4의 LCA 찾기
        System.out.println("노드 2와 4의 LCA: " + LCA(parentList, level, 2, 4));
    }

    public static int LCA(int[] parentList, int[] level, int n1, int n2) {
        // 1번
        if (level[n1] > level[n2]) {
            int temp = n1;
            n1 = n2;
            n2 = temp;
        }
        // 2번
        while (level[n1] != level[n2]) {
            n2 = parentList[n2];
        }
        // 3번
        while (n1 != n2) {
            n1 = parentList[n1];
            n2 = parentList[n2];
        }
        return n1;
    }
}