[Algorithm] (Java) 최소 공통 조상 LCA 트리

최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘

LCA(Lowest Common Ancestor)는 주어진 두 노드 a, b의 최소 공통 조상을 찾는 알고리즘이다.

예를 들어 아래의 트리에서 5번과 6번의 최소 공통 조상 LCA는 2번 노드이다.

일반적인 LCA 풀이방법

1. 1번 루트노드를 기준으로 DFS 탐색을 하면서 각 노드의 트리의 높이(h)와 부모 노드(parent)를 저장한다.
2. LCA 를 구하기 위한 a, b 노드가 주어지면 해당 두 노드의 h를 일정하게 맞춘다. (a의 높이 == b의 높이)
3. 높이가 맞춰졌으면 각 부모 노드가 일치할 때 까지 비교하여 구한다. (최대 LCA는 루트노드 1)

LCA를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게 되면 엄청 많은 반복을 해야할 수 있고 중복 연산을 하게 될 수도 있다. 그러면 O(NM) 의 시간복잡도를 갖게 되어 범위가 더 크게 주어진다면 속도는 느려질 것이다.

 

그래서 범위가 더 큰 데이터를 다뤄야 할 경우 더 효율적인 방식을 사용하여 구해야한다.

---

탐색 방법

1. 희소 테이블(Sparse table)이라는 개념을 이용하여 각 노드와 상위 노드(부모 노드)에 대한 정보를 담는다.
2. 노드의 정보란 각 노드가 어떻게 연결되어 있는지, 그리고 노드의 깊이는 어느 정도인지를 담는다. 
3. 쿼리로 들어오는 두 노드를 통해 판별한다.
4. Node A와 B가 입력으로 들어올 때 B를 더 하위노드라고 가정한다.
5. 두 노드의 레벨을 비교했을 때, B가 더 상위 노드라면 두 값의 인덱스를 맞바꿔준다.
6. 두 노드의 레벨을 맞춰준다.
7. 두 노드의 레벨을 맞추고 같은 노드에 존재한다면 A값을 리턴한다. (B도 상관없다.)
8. 같은 노드가 아니라면 아직 서로의 LCA를 찾지 못한 것이다. 둘 모두의 높이를 맞춰 올려주며 LCA를 찾는다.
9. 둘의 레벨을 같은 레벨로 변경하면서 서로 다른 노드로 탐색을 시작한다.
10. 이때 서로 다른 부모를 갖고 있다면 그 다음 상위 레벨 노드로 둘 모두를 동시에 올려준다.
11. 이렇게 처리된 후 최종값이 두 노드의 LCA가 된다.

 

희소 테이블(Sparse Table)

배열을 이용해 만드는 DP table이다. 트리에 매우 적합하다. 어떤 노드에서 한 노드로 이동할 때 그 경로가 유일한 경우를 테이블에 저장해둔다. 예를들어 위 그림에서 14번 노드에서 1번 노드로 가는 길은 '14 - 8 - 7 - 3 - 0 - 1' 로 유일하다. 이러한 정보들을 저장하는 것이다.

 

하나하나 N * N 배열로 저장한다면 공간은 낭비가 된다. 오래 걸리기도 하고 배열 크기도 고정값으로 잡을 수 없기 때문이다. 따라서, 희소 테이블을 사용하는 것이다. 이때의 희소는 정보량을 적게 한다는 의미이고 필요한 정보만 추려 넣는다고 생각하면 된다.

 

기본적 구조는 2차원 배열이고 parent라는 배열로 선언할 것이다.

int[][] parent = new int[N][21];

N은 노드 갯수를 의미하며 21은 각 노드의 몇 (2^i)번째 부모인지를 나타낸다.

이진트리에서 전체 노드가 100만개 있다고 가정하면 대략 20레벨이면 충분하다.

그리고 아래 코드를 통해 각 노드마다 바로 상위 노드에 대한 번호를 저장한다.

 

static void dfs(int current, int depth) {
    visit[current] = true;
    deep[current] = depth;

    for (int next : tree[current]) {
        if (visit[next]) continue;

        parent[next][0] = current;
        dfs(next, depth + 1);
    }
}

그림과 같이 보면 parent[1][0] = 0 ~ parent[14][0] = 8 식으로 저장이된다.

 

이렇게 각 노드별 인접한 상위 노드 설정을 한 뒤에는 각 노드끼리 연결을 한다.

0번 노드는 14의 4번째 부모인데 위 코드에 따라 parent[14][3] = 0이어야 한다. 확인해보도록 하자.

 

static void connect() {
    for (int p = 1; p < 21; p++) {
        for (int cur = 0; cur < N; cur++) {
            parent[cur][p] = parent[parent[cur][p-1]][p - 1];
        }
    }
}

/*
	example input
    15
    0 1
    0 2
    0 3
    1 4
    4 9
    3 5
    3 11
    3 6
    3 7
    5 10
    7 12
    7 13
    7 8
    8 14
    1
    14 10
*/

확인해보면 위와 같은 결과를 얻을 수 있다.

 

row는 노드의 갯수인 N(15)이고 col은 임의로 지정한 레벨 크기(21)이다.

좌측 가장 하단 값이 8인데 이는 parant[14][0] = 8을 의미하고 그림과 비교했을 때 14의 부모인 8과 일치하다.

같은 방식으로 parent[13][0] = 7 ~ parent[0][0] = 0 까지 모두 채워져있다.

 

0번 노드는 부모 노드가 없기 때문에 자기 자신을 가리키고 있고 이와 같은 값을 갖는 1, 2, 3 번 노드는 0번이 첫번째 부모 노드이기 때문에 0을 값으로 갖게된다.

 

parent[14][1] = 7을 확인해보면 이는 14 노드의 2번째 부모가 7이라는 것을 의미한다.

그렇다면 14노드의 세번째 부모의 값도 그림에서처럼 3으로 저장되어야 하는 것이 아닐까? 왜 0으로 저장되어있을까? 하지만 지금 있는 정보만으로도 모든 탐색이 가능하다. 이것이 희소 테이블의 장점이다.

 

14번에서 0번(4번째 부모)까지 탐색하는 순서를 살펴보도록 하자.

1. 14번의 두 번째 부모의 값이 7인 것을 알고 있다. 찾고자 하는것은 14번의 4번째 부모이다.
2. 7이라는 값을 가져와서 7번 노드의 부모를 탐색한다.
3. 다음은 parent[7][1]을 찾는다. 해당 값은 0이다. 7의 (2^1)번째 부모는 0번이라는 뜻이다.
4. 이런식으로 두번만에 4번째에 있는 최상위 부모 노드를 찾을 수 있다.

위 탐색과정에서 col 값은 실제로 1씩이 아닌 2의 제곱수 씩 움직인다는 사실을 알 수 있다. 그렇다면 2의 제곱수 씩 움직인다면 홀수나 2의 제곱수가 아닌경우는? 이는 이진수 즉 비트 연산으로 처리가 가능하다. 6번째 부모를 찾는다고 가정하면 이진수로 110 이고 이는 4번째에서 한번, 2번째에서 한번 뛰면 해결된다. 아래 그림으로 확인해보자.

 

이러한 경우 희소 테이블은 아래와 같이 구성된다.

0번은 14번 노드의 6번째 부모이다.

1. 6의 2진수는 110이다.
2. 1, 2번 인덱스만 사용할 것을 예상할 수 있다.
3. 우선 사용할 값은 parent[14][2] 이다.
4. 2 ^ 2만큼 점프를 하면 6번째라는 값을 넘지 않으니 해당 값 4를 갖고 점프한다.
5. 확인 결과, 4번 노드는 14의 4번째 부모이다.
6. 따라서 parent[4][1]의 값을 참조해보면 이는 0이다.
7. 이렇게 2의 제곱수가 아니더라도 2진수 표현식에 맞춰 순차 탐색이 가능하다.

이렇게 connect, dfs를 통해 희소 테이블을 구성 및 분석을 완료했다.

 

이제, 두 노드의 깊이를 결정해야한다. 입력으로 들어오는 각 노드의 깊이를 알 수 없기 때문이다.

깊이를 알아야 서로의 높이를 맞추고 상위 레벨 방향으로 LCA를 찾으며 두 노드를 계속해서 유도할 수 있기 때문이다. 

 

if (deep[node1] > deep[node2]) {
    int tmp = node1;
    node1 = node2;
    node2 = tmp;
}

 

노드들의 깊이 정보를 저장한 deep 배열을 통해 두 노드의 깊이를 비교한다.

node1과 node2 중 깊이가 더 깊은 노드를 깊이가 낮은 노드에 높이를 맞춰준다. 다시 말하자면 위 코드는 swap을 통해서 깊이가 더 깊은 노드를 낮은 노드의 높이로 맞춰준다고 보면된다. node1이 node2의 값을 갖고 node2가 node1의 값을 갖는다. 이제 아래에서 다시 이것을 활용할 것이다.

 

for (int i = 20; i >= 0; i--) {
    int jump = 1 << i;
    if (deep[node2] - deep[node1] >= jump) node2 = parent[node2][i];
}

 

 

최대 레벨에서부터 하나씩 줄여가며 점프를 하는데, 스왑한 결과로 node2가 원래 node1의 값 즉, 더 깊은 깊이의 노드 깊이를 갖고 있다. 이를 낮은 노드의 깊이를 갖고 있는 node1, 원래 node2의 값을 빼주고 이것이 jump 하는 값보다 크거나 같아지면 node2의 jump값만큼 부모를 확인한다. 쉽게 말하자면 node2에서 node1노드의 레벨을 빼주고 그만큼 뛰어오르고, 그 뛰어 오른 곳에서 14번 노드의 부모를 찾는 반복 동작이다. 이해가 어려울 수 있으니 차근차근 의미를 곱씹으며 확인해야한다. (이해안되서 몇번이고 코드랑 설명 읽음...)

 

다음으로는 레벨을 맞춰주었으니 최종적으로 LCA를 찾아준다. 

 

static int LCA(int node1, int node2) {
    if (deep[node1] > deep[node2]) {
        int tmp = node1;
        node1 = node2;
        node2 = tmp;
    }

    for (int i = 20; i >= 0; i--) {
        int jump = 1 << i;
        if (deep[node2] - deep[node1] >= jump) node2 = parent[node2][i];
    }

    if (node1 == node2) return node1;

    for (int i = 20; i >= 0; i--) {
        if (parent[node1][i] == parent[node2][i]) continue;

        node1 = parent[node1][i];
        node2 = parent[node2][i];
    }

    return parent[node1][0];
}

 

최종코드

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

/*
sample input

15
0 1
0 2
0 3
1 4
4 9
3 5
3 11
3 6
3 7
5 10
7 12
7 13
7 8
8 14
3
4 3
10 7
12 14

 */
public class LCA {
    static ArrayList<Integer>[] tree;
    static int[][] parent;
    static int[] deep;
    static boolean[] visit;

    static int N;
    static final String NEW_LINE = "\n";

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

        N = Integer.parseInt(br.readLine());

        tree = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            tree[i] = new ArrayList<>();
        }

        parent = new int[N][21];
        deep = new int[N];
        visit = new boolean[N];

        int loop = N - 1;
        while (loop-- > 0) {
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            tree[node1].add(node2);
            tree[node2].add(node1);
        }

        dfs(0, 0);
        connect();

        StringBuilder sb = new StringBuilder();
        int Q = Integer.parseInt(br.readLine());

        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            sb.append(LCA(node1, node2)).append(NEW_LINE);
        }

        System.out.println(sb.toString());
    }

    static int LCA(int node1, int node2) {
        if (deep[node1] > deep[node2]) {
            int tmp = node1;
            node1 = node2;
            node2 = tmp;
        }

        for (int i = 20; i >= 0; i--) {
            int jump = 1 << i;
            if (deep[node2] - deep[node1] >= jump) node2 = parent[node2][i];
        }

        if (node1 == node2) return node1;

        for (int i = 20; i >= 0; i--) {
            if (parent[node1][i] == parent[node2][i]) continue;

            node1 = parent[node1][i];
            node2 = parent[node2][i];
        }

        return parent[node1][0];
    }

    static void dfs(int current, int depth) {
        visit[current] = true;
        deep[current] = depth;

        for (int next : tree[current]) {
            if (visit[next]) continue;

            parent[next][0] = current;
            dfs(next, depth + 1);
        }
    }

    static void connect() {
        for (int p = 1; p < 21; p++) {
            for (int cur = 0; cur < N; cur++) {
                parent[cur][p] = parent[parent[cur][p-1]][p - 1];
            }
        }
    }

    static void print_parent() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 21; j++) {
                System.out.print(parent[i][j] + " ");
            }
            System.out.println();
        }
    }

    static void print_tree_info() {
        for (int i = 0; i < tree.length; i++) {
            System.out.print(i + " : ");
            for (int j = 0; j < tree[i].size(); j++) {
                System.out.print(tree[i].get(j) + " ");
            }
            System.out.println();
        }
    }
}

시간 복잡도는 희소 테이블을 이용한 N개 노드 탐색 : logN, 쿼리 개수 :Q 로 총 O(QlogN)이다.

 

 

---

출처

[알고리즘] 최소 공통 조상 LCA 트리 - DP & 세그먼트 트리 (Java)

 

5. LCA, Lowest Common Ancestor (최소 공통 조상)