18. 최소 공통 조상 (LCA: Lowest Common Ancestor) 2

앞에서 최소 공통 조상(이하 LCA) 알고리즘을 통해 트리 내 두 노드의 공통 조상을 찾는 방법을 설명드린 적이 있었습니다. 트리 내 두 노드의 가장 가까운 조상을 찾는 LCA 알고리즘을 통하여 노드가 공유하는 조상 노드 중 가장 깊은 노드를 찾는 방법을 알게 되었습니다. 가장 원초적 형태의 LCA 알고리즘도 물론 강력한 기능을 갖고 있는 알고리즘이지만 이를 강화시킨 버전의 LCA 알고리즘을 이번 챕터에서 말씀드리려고 합니다.

크기가 그렇게 크지 않은 트리에서는 특정 노드에서 조상을 찾기 위해 올라가는 과정이 그렇게 멀지 않습니다. 두 노드를 비교하여 깊이가 더 깊은 노드의 깊이를 상대적으로 깊이가 얕은 노드에 맞춰주고, 부모로 올라가는 과정을 몇 번 거치면 쉽게 LCA를 구할 수 있었습니다. 문제가 되는 것은 트리의 노드 수 가 10만개 이상으로 크기가 커지는 경우입니다. 특히 트리의 노드들이 균등하게 분포되어 있는 것이 아니라 사향트리와 같이 한쪽으로 쭉 치우쳐져서 한줄로 서버리는 경우에는 탐색에 드는 시간이 O(N)이 되는 등 비효율적인 부분이 발생하게 됩니다.

이러한 비효율을 극복하기 위하여 우리는 조상을 탐색할 때에 조상들을 접어서 탐색하는 방식을 취하게 됩니다. 만일 조상과 현재 노드의 거리가 100 이라면 100이라는 거리를 단순하게 1번째 조상, 즉 부모를 보고 그 부모의 부모를 보고 또 그 부모에 부모에 보모를 봐서 100번을 세는 것이 아니라 100 = 64(2^6) + 32(2^5) + 4(2^2) 과 같이 한 번에 여러 칸을 뛰어넘어서 3번만에 찾는 것이지요. 이것이 가능해지려면 현재 노드의 64번째 위의 조상, 그리고 64번째 위 조상의 32번째 위 조상, 그리고 마지막으로 64번째 조상의 32번째 조상의 4번째 조상 정보를 갖고 있으면 됩니다. 즉 이동순서가 현재노드 -> 64번째 조상 -> 32번째 조상 -> 4번째 조상으로 이어지는 것입니다. 그렇다면 우리는 이 정보들을 어떻게 알 수 있을까요.

이 정보는 동적계획법을 이용하여 구해놓습니다. 동적계획법은 간단히 말하자면 기본조건으로 주어진 기본값과 문제를 확장시켜주는 점화식을 이용하여 우리가 원하는 정답을 구하는 알고리즘입니다. 전체 문제를 하나로 보는 것이 아니라 쪼개서 더 작은 문제로 그리고 더 작은 문제로 나누고 이를 기본값만큼 축소시킨뒤 점화식을 이용하여 기본값보다 큰 문제를 풀고 또 그 결과로 더 큰 문제를 푸는 방식을 통해 전체 문제의 최적해를 구하는 것이죠. 이 문제는 동적계획법 문제가 아니기 때문에 설명은 여기까지 하겠습니다. 

이 문제에서는 동적계획법을 이용하여 루트 노드부터 점차적으로 확산해가면서 각 노드들의 조상 정보를 저장해줄 것입니다. 즉 시작은 각 노드들의 부모를 먼저 저장하는 것이 될 것이고, 이 정보들을 이용하여 두 단계 앞의 조상을 구할 것입니다. 노드들의 부모정보가 갱신된다면 우리는 부모를 타고 가서 부모의 부모 정보를 알 수 있기 때문에 두 단계 앞의 조상 정보를 알 수 있게 되는 것입니다. 그 다음에는 두 단계 앞 조상 정보가 전부 갱신되어 있다면, 이를 이용하여 두 단계 조상의 두 단계 조상도 알 수 있게 됩니다. 이렇게 되면 노드들의 4단계 위 조상 정보를 알 수 있게 됩니다. 이와 같은 방식으로 노드 입장에서 자기 깊이에서 가질 수 있는 2의 N승에 해당하는 조상들의 정보를 완성해놓을 수 있는 것입니다.

만일 위와 같은 크리가 있다면 보라색 노드의 부모는 초록색 노드가 될 것이고, 초록색 노드의 부모는 붉은색 노드가 될 것입니다. 즉 부모의 부모를 찾게 되면 두 단계 부모를 찾게 되는 것입니다. 보라색 노드의 두 단계 조상노드는 붉은색 노드이며, 우리는 이를 앞의 단계에서 이미 알 수 있었기 때문에 미리 저장해두었을 것입니다. 마찬가지로 붉은색 노드의 두 단계 부모는 검은색 노드가 되며, 우리는 이 정보 또한 미리 저장해두었습니다. 이렇게하여 미리 네단계 앞의 조상정보까지 찾아내어 저장하는 것입니다. 트리의 최대 깊이가 4보다 큰 값이어도 위의 작업을 반복적으로 진행한다면 모든 2^N 단계 위의 노드 정보들을 저장할 수 있을 것입니다.

정보를 다 저장하고 나면 이를 활용하여 LCA를 구하는 작업을 진행합니다. 조상을 찾을 때 2^N으로 압축하는 과정만 제외한다면 기존의 LCA를 찾는 방식과 거의 차이가 없습니다. 일단 선택된 두 노드 중 깊이가 더 깊은 노드를 선택한 뒤 깊이가 얕은 노드와 같은 깊이를 갖는 조상 노드로 그 위치를 조정해줍니다. 위치를 조정해줄 때는 앞에서 100을 2^N의 합으로 표현하였듯이 깊이의 차이보다 작은 2^N의 숫자 중 가장 큰수를 선택하여 그 숫자만큼의 조상으로 점프시켜줍니다. 그렇게 하고도 깊이 차이가 나게 되면 마찬가지로 점프한 노드에서 또 다시 차이 안에 들어올 수 있는 2^N 숫자중 가장 큰수를 이용하여 그만큼의 조상 값으로 점프시킵니다. 이렇게 이동시키게 되면 두 노드는 이제 같은 깊이를 갖게 됩니다. 이때 만약 두 노드가 만났다면 둘 중 한 노드가 다른 노드의 조상이었다는 것이므로, 해당 노드가 LCA라는 사실을 알 수 있게 됩니다. 만일 깊이가 같아졌음에도 두 노드가 만나지 못했다면 제3의 다른 노드가 LCA가 될 것이라는 뜻이기 때문에 두 노드를 조상노드로 이동시키는 작업을 진행합니다. 이 작업 또한 기존의 LCA 알고리즘과 동일한 것이지만 차이가 하나 있는데 둘을 조상 노드로 당겼을 때 만나게되는 노드 바로 직전 노드까지만 위로 이동시킨다는 것입니다. 두 노드의 공통 조상을 찾을 때 가질 수 있는 최대 조상부터 계산을 시작한다고 하면, 루트 노드이든 다른 어떤 노드이든 가질 수 있는 공통 조상중 가장 깊이가 얕은 조상을 선택할 가능성이 매우 높습니다. 그렇기 때문에 두 노드의 '최저' 공통 조상을 찾으려면 둘이 만나기 직전까지만 위로 당기는 작업을 한뒤 만나기 직전 두 노드의 부모를 선택하면 그 값이 바로 최저 공통 조상이 되는 것입니다.

실제로 문제를 풀어보면서 LCA 알고리즘이 어떻게 구현되는지 확인해보겠습니다.

11438번: LCA 2

https://www.acmicpc.net/problem/11438

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.StringTokenizer;

public class Main {

  private static ArrayList<Integer>[] con;

  private static int[] tree;

  private static final int MAX_N = 100000;

  private static final int MAX_D = 17;

  private static int[][] par;

  private static int tmp;

  private static int A;

  private static int B;

  public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = null;

    par = new int[MAX_D + 1][MAX_N + 1];

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

    con = new ArrayList[N + 1];

    tree = new int[N + 1];

    for (int i = 1; i <= N; i++) {

      con[i] = new ArrayList<Integer>();

    }

    for (int i = 1; i < N; i++) {

      st = new StringTokenizer(br.readLine().trim());

      A = Integer.parseInt(st.nextToken());

      B = Integer.parseInt(st.nextToken());

      con[A].add(B);

      con[B].add(A);

    }

    for (int i = 1; i <= N; i++) {

      tree[i] = -1;

    }

    dfs(1, 0);

    int M = Integer.parseInt(br.readLine().trim());

    for (int i = 1; i <= M; i++) {

      st = new StringTokenizer(br.readLine().trim());

      A = Integer.parseInt(st.nextToken());

      B = Integer.parseInt(st.nextToken());

      System.out.println(lca(A, B));

    }

  }

  private static void dfs(int node, int depth) {

    if (tree[node] != -1)

      return;

    tree[node] = depth;

    for (int next : con[node]) {

      if (tree[next] != -1)

        continue;

      par[0][next] = node;

      for (int i = 1; i <= MAX_D; i++) {

if(par[i - 1][next] == 0) break;

par[i][next] = par[i - 1][par[i - 1][next]];

}

        

      dfs(next, depth + 1);

    }

  }

  private static int lca(int a, int b) {

    if (tree[a] > tree[b]) {

      tmp = a;

      a = b;

      b = tmp;

    }

    for (int i = MAX_D; i >= 0; i--) {

      if (tree[b] - tree[a] >= (1 << i))

        b = par[i][b];

    }

    if (a == b)

      return a;

    for (int i = MAX_D; i >= 0; i--) {

      if (par[i][a] != par[i][b]) {

        a = par[i][a];

        b = par[i][b];

      }

    }

    return par[0][a];

  }

}