PrerequisitePermalink

• DFS
• Sparse Table

LCAPermalink

LCA는 트리에서의 테크닉인데, 말 그대로 어떤 두 노드의 공통된 조상들 중에 가장 가까이 있는 노드를 찾아오는 것이다.

두 노드의 LCA는 그 두 노드중 있을 수도 있다. 두 노드중 한 노드가 다른 한 노드의 조상일 수 있기 때문이다.

naive하게 찾으면, 두 노드중 높이가 낮은 것부터 계속 하나씩 올리다 보면 언젠가는 LCA를 찾을 것이므로 LCA를 찾는 쿼리가 $O(N)$가 되지만, 우리가 다룰 알고리즘은 $O(\log N)$에 그러한 쿼리를 수행할 수 있게 해준다.

Sparse Table 을 먼저 공부를 해야하는데, Sprase Table을 정확히 이해했다면 LCA는 사실 단순하다.

하지만 LCA는 그저 공통 조상을 찾는것보다도 활용도가 무궁무진한 알고리즘이다. 가장 간단한 예시로, 트리에서 두 정점간의 최단 거리를 찾는데도 쓰인다.

알고리즘Permalink

BOJ 11438 - LCA 2 문제를 풀어보자.

예전엔 플레티넘 4였던 것 같은데, 언제 플레티넘 5로 난이도가 떨어졌지

전처리Permalink

$p[K][N]$ 을 관리해주며 $p[k][i]$ 가 노드 $i$의 $2^k$ 번째 조상을 가리키게 만들자. 만약 $2^k$ 번째 조상이 없다면 $-1$ 같은 값을 할당해주면 된다.

$p$ 테이블은 $O(N\log N)$에 채울 수 있다.

우선 한 번의 DFS로 $p[0][i]$ 를 채울 수 있고, 각 노드의 $level$ 도 기록해두면 좋다. $level[root]=0$ 이다.

vvi p(K, vi(n, -1));  
vi level(n, -1);  
function<void(int)> fn = [&](int i) {  
   for (int j: e[i]) if (level[j] == -1)
     level[j] = level[i] + 1, p[j][0] = i, fn(j);  
};  
level[0] = 0;  
fn(0);

이제 $p$ 테이블을 채우는 코드를 보자.

$p[0][i]$ 는 DFS과정에서 미리 채워져 있으므로 $k=1$ 부터 채워나가면 된다.

$p$를 채우는 방법은 $i$의 $2^k$ 번째 조상은 $i$의 $2^{k-1}$ 번째 조상의 $2^{k-1}$ 번째 조상임을 이용하는 것이다.

이렇게 $p$를 $O(N\log N)$에 채워줄 수 있다.

for (int k = 1; k < K; k++)  
   for (int i = 0; i < n; i++)  
      if (p[k - 1][i] != -1)  
         p[k][i] = p[k - 1][p[k - 1][i]];

쿼리Permalink

이제 전처리는 끝났고 실제 LCA 쿼리를 날려보자.

노드 $u,\,v$ 의 LCA를 찾는다고 하자. 다음과 같은 단계로 이루어진다.

• $u,\,v$의 $level$을 동일하게 맞춘다.
  • 이 때, $u=v$ 가 된다면 알고리즘이 종료된다.
• $k$를 $K \to 0$ 으로 순회하며 $u$와 $v$가 서로 다른 $2^k$ 번째 조상을 갖고 있다면, $u$와 $v$를 $2^k$ 번째 조상으로 변경한다.
• $u$나 $v$의 부모 노드가 LCA이다.

일반성을 잃지 않고 $level[u] > level[v]$ 라고 하자. $d=level[u]-level[v]$ 만큼 $d$ 를 이진수로 표현하여 $1$이 있는 위치들이 나올 때 마다 $2^k$ 만큼 $u \coloneqq p[k][u]$ 해주어 $v$와 같은 높이를 맞춘다. $O(\log N)$ 이 걸린다.

만약 원래 $u$와 $v$가 조상-자손 관계였다면 여기서 $u=v$ 여야 한다. 그래서 알고리즘이 종료된다.

그렇지 않다면 $k$ 를 내림차순으로 순회하며 $u$와 $v$의 $2^k$ 번째 조상이 같지 않을 때마다 그 조상들로 변경해준다.

내림차순으로 순회해야하는 이유는 $2^{k+1}$ 번 째 조상까지 같다가 $2^k$ 번 째 조상이 처음으로 서로 다를 때 둘 다 그 조상으로 변경하면 더 이상 $2^k$ 이상의 다른 조상이 나올 일이 없기 때문이다. 만약 그렇다면 $2^{k+1}$ 번 째에 이미 조상이 달랐어야 하므로 모순이다.

마지막으로, 조상이 같지 않을 때 까지 이를 반복했고, $k$는 $2^0$까지 검사했으므로 항상 $u$와 $v$는 한 부모의 다른 두 자식이라는 결과가 되기 때문에, 둘 중 아무거나의 부모가 LCA가 된다.

cin >> u >> v, u--, v--;  
if (level[u] < level[v]) swap(u, v);  
for (int d = level[u] - level[v], k = 0; d; k++, d >>= 1)  
   if (d & 1) u = p[k][u];  
if (u == v) {  
   cout << u + 1 << endl;  
} else {  
   for (int k = K - 1; k >= 0; k--)  
      if (p[k][u] ^ p[k][v]) u = p[k][u], v = p[k][v];  
   cout << p[0][u] + 1 << endl;  
}

BOJ 11438 - LCA 2 문제의 전체 코드는 다음과 같다.

const int K = 20;  
void solve() {  
   int n, m, u, v;  
   cin >> n;  
   vvi e(n);  
   for (int i = 0; i < n - 1; i++) cin >> u >> v, u--, v--, e[u].pb(v), e[v].pb(u);  
   cin >> m;  
  
   vvi p(K, vi(n, -1));  
   vi level(n, -1);  
   function<void(int)> fn = [&](int i) {  
      for (int j: e[i]) if (level[j] == -1) level[j] = level[i] + 1, p[0][j] = i, fn(j);  
   };  
   level[0] = 0;  
   fn(0);  
  
   for (int k = 1; k < K; k++)  
      for (int i = 0; i < n; i++)  
         if (p[k - 1][i] != -1)  
            p[k][i] = p[k - 1][p[k - 1][i]];  
  
   while (m--) {  
      cin >> u >> v, u--, v--;  
      if (level[u] < level[v]) swap(u, v);  
      for (int d = level[u] - level[v], k = 0; d; k++, d >>= 1)  
         if (d & 1) u = p[k][u];  
      if (u == v) {  
         cout << u + 1 << endl;  
      } else {  
         for (int k = K - 1; k >= 0; k--)  
            if (p[k][u] ^ p[k][v]) u = p[k][u], v = p[k][v];  
         cout << p[0][u] + 1 << endl;  
      }  
   }  
}

LCA 활용 1 - 트리에서 두 정점의 최단 거리Permalink

BOJ 1761 - 정점들의 거리 문제는 딱 이 활용에 대한 연습 문제이다.

위 LCA를 전처리 하는 과정에서, $p$ 배열 말고 $d$ 배열도 같이 관리한다 하자.

그럼 LCA를 찾는 과정에서 $u,\,v$를 업데이트 해줄 때 정답에 $d$의 값도 동일하게 더해주면 쉽게 정답을 구할 수 있다.

O(1) LCAPermalink

Euler tour technic 를 활용하면 $O(1)$ 로도 LCA쿼리를 날려버릴 수 있다.

고난도 연습문제Permalink

LCA에 대해 깊은 생각을 할 수 있게 해주는 연습문제 두 개를 추천한다.

BOJ 17399 - 트리의 외심

BOJ 15480 - LCA와 쿼리