[Algorithm] LCA

공통 조상 구하기

트리 구조에서 임의의 두 노드가 가지는 가장 가까운 공통 조상을 찾아내는 알고리즘이다.

위의 그림에서 8과 11의 공통 조상은 2, 1 이 존재하며 최소 공통 조상은 2임을 쉽게 알 수 있다.

가장 단순하게 구한다면 구하고자하는 두 노드의 깊이를 한 칸씩 올려 맞춰준 후 동시에 한 깊이씩 올라가다가 만나는 경우를 찾으면 된다. 이는 O(Depth) 이다. 이 때 두 노드의 깊이를 맞춰줄 때 O(Log(Depth)) 로 표현하기 위한 것이 LCA 이다.

LCA

각 노드마다 Parent[k] 를 가지고 2^k 번째 조상의 노드 번호를 저장하는 방법이다. 이를 위해 Parent[i][k] 2차원 배열이 필요하다. 또한 두 노드의 시작 깊이를 알아야하기 때문에 깊이를 저장하는 배열 depth[i] 가 필요하다.

구현

static int lca(int a, int b) {
  if (depth[a] < depth[b]) { // 깊이가 낮은 쪽을 기준으로 맞춘다.
    int temp = a;
    a = b;
    b = temp;
  }

  for (int i = K - 1; i >= 0; i--) {
    if (Math.pow(2, i) <= depth[a] - depth[b]) {
      a = parents[a][i];
    }
  }

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

먼저 깊이의 높낮이를 항상 맞춰준다. 그리고 두 깊이의 차이를 2^k 에 가장 가깝게 맞춰서 빠르게 두 노드의 깊이를 맞춰준다. for 문 안에서 a 를 b에 가까운 조상으로 계속해서 갱신해나간다. 두 노드의 깊이가 맞춰졌다면 다시 처음으로 같은 노드를 가르키기 전까지 log(n) 으로 접근한다.

static void makeParents() {
  for (int i = 1; i < K; i++) {
    for (int j = 1; j <= N; j++) {
      parents[j][i] = parents[parents[j][i - 1]][i - 1];
      }
  }
}

Parent 2차원 배열은 DP 를 사용해서 만든다.