[알고리즘] 최소 공통 조상 - LCA(Lowest Common Acestor)

1. LCA (Lowest Common Acestor) 알고리즘이란?

---

트리 구조에서 최소 공통 조상을 찾는 알고리즘으로, 두 정점 (u, v)에서 가장 가까운 공통 조상을 찾는 알고리즘입니다.

아래와 같은 트리가 있다고 해보겠습니다.

[그림 1] 최초 트리의 모양

(u, v)의 조상을 LCA(u, v)라고 하면, LCA(2, 7)은 무엇일까요? 🤔

[그림 2] LCA(2, 7)

몇 번 더해보겠습니다. LCA(9, 6)은 무엇일까요?

[그림 3] LCA(9, 6)

마지막으로, LCA(12, 14)는 무엇일까요?

[그림 4] LCA(12, 14)

LCA(12, 14) = LCA(14, 12) = 12 라는걸 알 수 있습니다. 최소 공통 조상이라는게 무엇인지 이해되셨나요? 🙂

2. LCA 알고리즘 동작 과정

---

우선 가장 먼저 해야할 건 당연히 입력받은 정점과 간선으로 트리를 구성하는 것입니다.

다음으로, depth와 조상 노드를 같이 구해야 하는데 이때, 조상 노드는 2^K 번 째의 모든 조상 노드를 구합니다.

[그림 5] depth와 2^K번 째 조상 노드

2^0번째 조상 노드는 자기 바로 위의 부모 노드이고, 2^1번째는 자기 부모의 부모 노드가 된다.

3. 코드

---

트리를 만들었다면, 각 노드의 2^K 번 째 조상 노드를 depth[] 배열에 담아둡니다.

그런 다음, LCA(a, b)에 대해 depth를 맞춘 후, 둘의 공통 조상을 구합니다.

class Main {
 
    // ...생략
 
    private static int lca(int a, int b) {
        if (depth[a] < depth[b]) { // 깊이가 낮은 쪽을 기준으로 맞춘다.
            int temp = a;
            a = b;
            b = temp;
        }
 
        //더 깊은 a를 2승씩 점프하며 두 노드의 depth를 맞춘 후, 맞춘 depth의 조상 노드로 대체한다.
        for (int i = K - 1; i >= 0; i--) {
            if (Math.pow(2, i) <= depth[a] - depth[b]) {
                a = parents[a][i]; // a를 2^i 번 째 조상 노드로 대체한다.
            }
        }
 
        // depth 맞춘 후 대체한 조상 노드가 b와 같다면. 즉, a의 조상노드가 b라면 종료한다.
        if (a == b) return a;
 
        // 이제 두 노드는 같은 depth를 가지기 때문에
        // 같이 2승씩 점프시키며 공통부모 바로 아래까지 올린다.
        for (int i = K - 1; i >= 0; i--) {
            if (parents[a][i] != parents[b][i]) {
                a = parents[a][i];
                b = parents[b][i];
            }
        }
        return parents[a][0];
    }
    private static void fillParents() {
        for (int i = 1; i < K; i++) {
            for (int j = 1; j <= N; j++) {
                parents[j][i] = parents[ parents[j][i - 1] ][i - 1];
            }
        }
    }
    private static void dfs(int from, int cnt) {
        depth[from] = cnt++;
        
        for (Integer next : tree.get(from) {
            if (depth[next] == 0) {
                dfs(next, cnt);
                parents[next][0] = from;
            }
        }
    }
}

4. 참고자료

---

[1] https://www.crocus.co.kr/660