골드에그

LCA 알고리즘이란,

트리 상의 정점 U 와 V 가 주어질 때 U 와 V 에서 가장 가까운 공통 조상을 찾는 알고리즘이다.

위 LCA 그래프 예시에서 24 와 26 의 LCA (최초 조상) 은 5 이다.

어떻게 조상을 찾는 것일까?

조상을 찾는 방법을 step-by-step 으로 표현한다면 다음과 같다.

0 . U 노드와 V 노드를 정한다. (깊이가 더 큰 노드를 V로 정한다.)

1 . U 노드의 깊이와 V 노드의 깊이가 같아질 때까지 깊이가 더 깊은 노드(V)를 자신의 조상으로 바꾸어 준다.

2 . U 노드와 V 노드의 조상이 같아질 때까지 자신의 조상으로 바꾸어 준다.

1 번 과정, 2 번 과정 모두 한 단계씩 조상을 올리게 되면 O(N) (깊이를 N이라 두었을 때) 의 복잡도를 가지게 된다.

조금 더 빠르게 트리를 탐색하기 위해 $2^{x}$ 번째에 해당하는 부모만 기억하고 중학교 때 배운 아래 지수법칙

$2^{x+1}=2^{x}*2$ 수식을 활용한다. 수식에서 * 2 부분을 만족하려면 조상노드를 한 번 더 그 크기만큼 올라가야 한다. 

따라서,

u 노드의 $2^{x}$ 번째에 해당하는 부모를 parent[u][x] 라고 할 때, parent[u][x] = parent[parent[u][x-1]][x-1] 라는 점화식이 성립한다. 점화식이 만들어졌으니 Bottom-Up DP 로 parent 테이블을 만들어주면 된다.

총 루틴 정리

알고리즘의 중요 부분은 모두 나왔다. 총 루틴을 정리해보자.

1 . 그래프의 깊이를 구한다.

이 LCA 에서 사용하는 트리는 이진 트리이므로 높이는 log2(N) + 1이다. 여기서 N은 총 그래프 노드의 개수.

(int)Math.ceil(Math.log(n)/Math.log(2)) +1;

2 . DFS 로 순회하면서 depth 배열과 parent[][0] 배열을 초기화한다.

3 . parent[x][y] 배열을 셋팅한다.

parent[x][y] = parent[parent[x][y-1]][y-1] 점화식이 성립하고 미래 값을 먼저 구하지 않아도 되므로 Bottom-up DP 로 구할 수 있다.

4 . LCA(a, b) 에서 b 가 더 깊도록 a 와 b 를 서로 바꾼다.

5 . b 깊이가 a 깊이와 같도록 부모 배열을 활용해 자신의 조상으로 바꾼다.

6 . 현재 부모가 같다면 리턴.

7 . 조상이 같을 때까지 조상을 거슬러 올라가기. 부모가 같다면 그 조상을 리턴.

자바 코드

자바코드는 다음과 같다.

public static class LCA {
    private int nodeCount;
    private List<Integer>[] adjacencyList;
    private int treeHigh;
    private int[] depth;
    private boolean[] memoization;
    private int[][] parent;

    public LCA(int nodeCount, List<Integer>[] adjacencyList) {
        this.nodeCount = nodeCount;
        this.adjacencyList = adjacencyList;
        this.memoization = new boolean[nodeCount+1];
        this.depth = new int[nodeCount+1];
        getTreeHigh();
        this.parent = new int[nodeCount+1][this.treeHigh];
    }

    private void getTreeHigh() {
        this.treeHigh = (int)Math.ceil(Math.log(nodeCount)/Math.log(2)) + 1;
    }
    private void init(int current, int treeHigh) {
        memoization[current] = true;
        depth[current] = treeHigh;
        for (int next : adjacencyList[current]) {
            // 메모이제이션
            if(memoization[next]) continue;
            init(next, treeHigh+1);
            parent[next][0] = current;
        }
    }
    private void makeParentArray() {
        for(int i=1; i<treeHigh; i++) {
            for(int j=1; j<nodeCount+1; j++) {
                parent[j][i] = parent[parent[j][i-1]][i-1];
            }
        }
    }
    public int run(int a, int b) {
        init(1,1);
        makeParentArray();
        // b 가 더 깊도록 설정
        if (depth[a] > depth[b]) {
            int temp = a;
            a = b;
            b = temp;
        }
        // 깊이가 동일하도록 b 를 옮김
        for (int i = treeHigh-1; i>=0; i--) {
            if ((1<<i) <= depth[b] - depth[a]) {
                b = parent[b][i];
            }
        }

        if(a==b) return a;

        for(int i=treeHigh-1; i>=0; i--) {
            if (parent[a][i] != parent[b][i]) {
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        return parent[a][0];
    }
}