LCA(Lowest Common Ancestor)

LCA 이해

---

• 출처 : https://velog.io/@syd1215no/자료구조-Tree-Graph

LCA란, 위 그림과 같이 트리를 이루고 있는 어떠한 노드 ‘E’와 ‘M’의 최소 공통 조상(Lowest Common Ancester)를 찾는 알고리즘이다.

간단하게 생각하면 노드 ‘E’에서 루트까지 올라오고 노드 ‘M’에서 루트까지 올라오면서 처음 겹치는 구간이 LCA임을 알 수 있다.

그러나, 노드의 개수를 $N$이라 하면 최악의 경우 $O(N^2)$의 시간 복잡도를 가지기 때문에 노드가 많아질 수록 시간에서 불리하다.

그래서 dp(동적계획법; dynamic programming)를 사용하여 해결하려고 한다.

먼저, 메모이제이션을 위한 2차원 변수를 하나 만들어준다.

• parent[node][i] : node에서 $2^i$번째 부모

$2^i$번째 부모라는 의미는 위의 그림을 가지고 설명하자면, 노드 ‘E’의 1번째($2^0$) 부모는 ‘B’이고 2번째($2^1$) 부모는 ‘A’이다. 이것을 parent 배열에는 다음과 같이 저장된다.

• parent['D'][0] = 'B'
• parent['D'][1] = 'A'

다른 노드 ‘K’의 parent배열에는 다음과 같이 저장되어야 한다.

• parent['K'][0] = 'E'
• parent['K'][1] = 'B'

‘K’의 3번째 부모 ‘A’는 $2^i$으로 나타낼 수 없기 때문에 저장할 수 없다

저장할 때 노드마다 계속 위로 올라가면서 저장하는 것은 좋지않다. 그래서 dp를 사용해서 이전값을 가져와 업데이트를 하는 것이다.

예를들면, ‘E’의 1번째 부모는 ‘B’이고, ‘B’의 1번째 부모는 ‘A’이므로 ‘E’의 2번째 부모는 ‘A’인 것을 바로 알 수있다. 즉, 다음의 점화식을 만족한다.

• parent['B'][i] = parent[parent['B'][i-1]][i-1]

이제, 아래 그림에서 ‘C’와 ‘G’의 LCA를 구하는 방법에 대해 이야기 하자.

가장 먼저 해야할 것은 ‘C’와 ‘G’의 높이를 맞추는 작업이다. 보통 더 깊은 노드를 올려서 구현한다.

‘G’의 $2^0$번째 부모 ‘F’, $2^1$번째 부모 ‘E’, $2^2$번째 부모 ‘A’가 저장되어 있으므로 ‘C’와 같은 깊이의 부모를 찾는다.

루트의 깊이를 0이라 하면 ‘C’의 깊이는 2이므로 ‘G’의 깊이 4에서 높이 2에 위치한 부모 ‘E’까지 올려준다.

이제 ‘C’와 ‘E’의 parent 배열을 통해 공통 조상을 찾아가면 된다.

아래는 노드마다 parent와 depth를 업데이트하는 코드이다.

vector<int> tree[MAX_NODE];
int depth[MAX_NODE];
int parent[MAX_NODE][LEN]; // LEN는 2^i가 최대 깊이만큼 존재해야 하므로 충분히 길게 잡아준다.
int max_depth;

void dfs(int node, int prt) { // dfs로 탐색하면서 depth와 parent를 저장해준다
  depth[node]=depth[parent]+1;
  parent[node][0]=prt;
	
  max_depth=max(max_depth,depth[node]);
	
  for(int i=1;i<=max_depth;i++) {
    int ancester=parent[node][i-1];
    parent[node][i]=parent[ancester][i-1];
  }

  for(auto it : tree[node]) { // 다음 자식으로 탐색
    int next=it;
    if(next!=parent) dfs(next,node);
  }
	
  return;
}

int LCA(int a, int b) { // 두 노드 a,b의 LCA를 반환하는 함수
  if(depth[a]!=depth[b]) {
    if(depth[a]>depth[b]) swap(a,b);

    for(int i=max_depth;i>=0;i--) { // 두 노드의 깊이를 맞추는 반복문
      if(depth[a]<=depth[b]) b=parent[b][i];
    }
  }

  int lca=a;
  if(a!=b) {
    for(int i=max_depth;i>=0;i--) {
      if(parent[a][i]!=parent[b][i]) {
        a=parent[a][i];
        b=parent[b][i];
      }
      // 맨 마지막은 공통조상부모의 자식으로 끝이나기 때문에 그들의 부모로 저장한다.
      lca=parent[a][i];
    }
  }

  return lca;
}

LCA 알고리즘의 성능

---

노드의 개수가 $N$개이면, 한 번 찾는데 $O(lgN)$의 시간 복잡도를 가지게 된다. 따라서, 쿼리가 $M$개일 때 시간 복잡도 $O(MlgN)$의 시간 복잡도를 가진다.