LCA - Lowest Common Ancestor
Prerequisite
- DFS
- Sparse Table
LCA
LCA는 트리에서의 테크닉인데, 말 그대로 어떤 두 노드의 공통된 조상들 중에 가장 가까이 있는 노드를 찾아오는 것이다.
두 노드의 LCA는 그 두 노드중 있을 수도 있다. 두 노드중 한 노드가 다른 한 노드의 조상일 수 있기 때문이다.
naive하게 찾으면, 두 노드중 높이가 낮은 것부터 계속 하나씩 올리다 보면 언젠가는 LCA를 찾을 것이므로 LCA를 찾는 쿼리가 $O(N)$가 되지만, 우리가 다룰 알고리즘은 $O(\log N)$에 그러한 쿼리를 수행할 수 있게 해준다.
Sparse Table 을 먼저 공부를 해야하는데, Sprase Table을 정확히 이해했다면 LCA는 사실 단순하다.
하지만 LCA는 그저 공통 조상을 찾는것보다도 활용도가 무궁무진한 알고리즘이다. 가장 간단한 예시로, 트리에서 두 정점간의 최단 거리를 찾는데도 쓰인다.
알고리즘
BOJ 11438 - LCA 2 문제를 풀어보자.
예전엔 플레티넘 4였던 것 같은데, 언제 플레티넘 5로 난이도가 떨어졌지
전처리
$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]];
쿼리
이제 전처리는 끝났고 실제 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 문제의 전체 코드는 다음과 같다.
LCA 활용 1 - 트리에서 두 정점의 최단 거리
BOJ 1761 - 정점들의 거리 문제는 딱 이 활용에 대한 연습 문제이다.
위 LCA를 전처리 하는 과정에서, $p$ 배열 말고 $d$ 배열도 같이 관리한다 하자.
그럼 LCA를 찾는 과정에서 $u,\,v$를 업데이트 해줄 때 정답에 $d$의 값도 동일하게 더해주면 쉽게 정답을 구할 수 있다.
O(1) LCA
Euler tour technic 를 활용하면 $O(1)$ 로도 LCA쿼리를 날려버릴 수 있다.
고난도 연습문제
LCA에 대해 깊은 생각을 할 수 있게 해주는 연습문제 두 개를 추천한다.
Comments