[알고리즘]LCA (Lowest Common Ancestor) 알고리즘

LCA 알고리즘

최소 공통 조상을 찾는 알고리즘
즉, 두 노드에서 가장 가까운 공통 조상을 찾는 알고리즘이다.

예를 들어, 위와 같은 상황에서
4와 10의 최소 공통 조상은 8,
6과 9의 최소 공통 조상은 2,
13과 8의 최소 공통 조상은 1이 된다.

---

알고리즘 진행 과정

우선적으로 이 알고리즘을 진행하기 위해서는
모든 노드에 대한 깊이과, 부모 노드가 저장되어있어야한다.

1. 두 노드의 깊이가 동일할 때까지 거슬러 올라감
2. 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감
3. 모든 LCA(a,b) 연산에 대하여 1~2의 과정의 반복

위의 그래프에서 6과 14의 최소 공통 조상을 구해보자.

6과 14의 깊이가 다르기 때문에 우선적으로 ①~② 과정을 진행한다.

부모 노드의 방향으로 거슬러 올라가 비교해도 13과 14의 깊이는 다르기 때문에 다시 한번 진행한다.

2와 14의 깊이는 동일하기때문에 더 이상 반복할 필요가 없다.
이제 조건문으로 깊이는 동일하지만, 두 수가 다른 경우 둘 중 어느것이든 부모노드를 구한다면
그게 바로 최소 공통 부모가 된다.

---

소스 코드 (java)

*코드는 LCA의 풀이로 대체

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static ArrayList<Integer>[] tree;
    static int[] parents, depth;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n + 1];
        parents = new int[n + 1];
        depth = new int[n + 1];

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

        Arrays.fill(depth, -1);
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree[a].add(b);
            tree[b].add(a);
        }

        dfs(1, 1, 0);
        m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(lca(a, b) + "\n");
        }
        System.out.println(sb);

    }

    public static void dfs(int cur, int dep, int parent) {
        depth[cur] = dep;
        parents[cur] = parent;

        for (int next : tree[cur]) {
            if (next != parent) {
                dfs(next, dep + 1, cur);
            }
        }
    }

    public static int lca(int a, int b) {
        int aDepth = depth[a];
        int bDepth = depth[b];

        while (aDepth != bDepth) {
            if (aDepth > bDepth) {
                a = parents[a];
                aDepth--;
            } else {
                b = parents[b];
                bDepth--;
            }
        }
        while (a != b) {
            a = parents[a];
            b = parents[b];
        }
        return a;
    }
}