[알고리즘] LCA 알고리즘

LCA(Lowest Common Ancestor) 알고리즘 이란?

• LCA 알고리즘은 트리에서 주어진 두개의 노드의 최소 공통 조상을 찾는 알고리즘이다.
• 예를 들어 아래 그림에서 5,6번 노드의 LCA는 2번 노드이다.
  

간단한 LCA 알고리즘 : O(N)

• 간단히 생각해볼 수 있는 LCA 알고리즘은 다음과 같다.

  1. 루트 노드를 기준으로 DFS를 통해 각 노드의 트리 높이와 부모 노드를 저장해준다.
  2. 두 노드의 높이를 맞춰준다.
  3. 부모노드가 일치할 때까지 각 노드의 부모노드로 이동시켜 준다.

• 위 알고리즘은 일반적인 트리에서는 문제가 없지만 편향트리(높이와 노드수가 비슷)에서는 O(N)의 시간복잡도를 보인다.
• 따라서, 수의 범위가 클 경우 O(logN) 알고리즘을 사용해야한다.

LCA + DP 알고리즘(Sparse Table 사용) : O(logN)

DP[a][b] : a노드에서 2^b번째 부모노드

• 위와 같은 DP테이블로 메모이제이션을 한다면 현재 노드에서 특정 부모 노드로 이동하기의 연산 횟수를 logN으로 줄일 수 있다.
• 예를 들어 부모노드에서 현재노드까지 거리가 100이면 64+32+4=100으로 총 3번의 연산을 통해 부모노드를 구할 수 있다.
• 이를 활용하여 아래와 같은 구현으로 알고리즘을 수행하면 O(logN)의 시간복잡도를 보인다.

구현1) DP배열의 2번째 인덱스 최대값 구하기

• 2번째인자 b는 2^b가 트리의 높이가 되므로 높이가 N일때 최대 b값을 구해준다.

public static int getMaxIndex() {
	return (int)Math.ceil(Math.log(N) / Math.log(2)) + 1;
}

구현2) DFS탐색을 통해 각 노드의 높이(depth)와 1번째 (2^0) 부모노드값 초기화 해주기

public static void init(int ind, int h, int before) {
        depth[ind] = h;
        for (int i = 0; i < map.get(ind).size(); i++) {
            int next = map.get(ind).get(i);
            if (next == before) continue;
            dp[next][0] = ind;  //다음 노드의 부모 노드를 현재 노드로 지정
            init(next, h+1, ind);
        }
}

구현3) 나머지 DP테이블 채우기

• DP[index][a] = index 노드의 2^a 번째 부모노드이다
• 2^a = 2^(a-1) + 2^(a-1)이므로 DP[index][a] = DP[DP[index][a-1]][a-1] 이라는 점화식이 도출된다.

public static void fillDp() {
        for (int i = 1; i < maxInd; i++) {
            for (int ind = 1; ind <= N; ind++)
                dp[ind][i] = dp[dp[ind][i-1]][i-1];
        }
}

구현4) LCA 구하기

• 위의 데이터들을 이용해서 LCA를 구하는 방법은 다음과 같다.

  1. 두 노드의 높이 맞춰주기
  2. 두 노드를 최소 공통 조상 자식 노드들까지 동시에 업데이트시킨다.
  3. 각 노드의 부모노드가 최소 공통 조상 노드가 된다.

public static int LCA(int a, int b) {
        //ah > bh로 세팅하기
        if (depth[a] < depth[b]) {
            int tmp = a;
            a = b;
            b = tmp;
        }

        //1. 높이 맞춰주기
        for (int i = maxInd-1; i >= 0; i--) {
            if (Math.pow(2, i) <= depth[a] - depth[b])
                a = dp[a][i];
        }

        if (a==b) return a;

        for (int i = maxInd-1; i >= 0; i--) {
            if (dp[a][i] == dp[b][i]) continue;
            a = dp[a][i];
            b = dp[b][i];
        }
        return dp[a][0];
    }