최소 공통 조상, LCA
최소 공통 조상, LCA
LCA (Lowest Common Ancestor, 최소 공통 조상)는 루트가 있는 트리에서 두 노드의 공통 조상 중 가장 깊은 노드를 찾는 알고리즘이다.
공통 조상이란 두 노드 $u$, $v$에 대해 루트에서 $u$로 가는 경로와 $v$로 가는 경로 모두에 포함되는 노드를 말한다. 그중 가장 깊은(== 루트에서 가장 먼) 노드가 최소 공통 조상이다.
활용
LCA는 두 노드 사이의 거리를 계산할 때 사용된다. $dist(u, v) = depth[u] + depth[v] - 2 \cdot depth[LCA(u, v)]$
또는 두 노드 간 경로에서의 최댓값 또는 최솟값을 구할 때 사용될 수 있다. LCA를 찾는 과정에서 최댓값 또는 최솟값을 갱신하며 올라가면 된다.
Naive 구현
가장 직관적인 방법은 두 노드의 깊이를 맞춘 뒤, 동시에 한 칸씩 올라가며 같은 노드에 도달할 때까지 반복하는 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int parent[100001];
int depth[100001];
void dfs(int cur, int par, int d) {
parent[cur] = par;
depth[cur] = d;
for (int nxt : adj[cur]) {
if (nxt == par) continue;
dfs(nxt, cur, d + 1);
}
}
int lca(int u, int v) {
// 먼저 깊이를 맞추고,
while (depth[u] > depth[v]) u = parent[u];
while (depth[v] > depth[u]) v = parent[v];
// 동시에 올라간다.
while (u != v) {
u = parent[u];
v = parent[v];
}
return u;
}
이 구현은 직관적이지만, 트리가 편향된 경우 두 노드의 깊이 차이가 최대 $O(N)$이 될 수 있다. 따라서 쿼리 하나에 $O(N)$, $Q$개의 쿼리에 대해 $O(NQ)$의 시간복잡도를 가진다.
희소 테이블을 이용한 LCA - Binary Lifting
희소 테이블(Sparse Table)이란 미리 $2^k$ 크기의 구간에 대한 정보를 전처리 해두어, 특정 구간에 대한 쿼리를 빠르게 처리하도록 하는 자료구조이다. 여기서는 ‘노드 $v$의 $2^k$ 번째 조상’을 전처리하는 데 사용된다.
Naive에서 한 칸씩 올라가는 것을 $2^k$칸씩 올라하도록 개선하는 기법이다. 각 노드에 대해 $2^k$번째 조상을 미리 전처리하면, 깊이를 맞추는 과정과 LCA를 찾는 과정 모두 $O(\log N)$에 수행할 수 있다.
핵심 아이디어
특정 노드의 조상을 저장하는 up 배열을 관리한다. up[k][v]은 노드 $v$의 $2^k$번째 조상을 저장한다.
이 테이블은 다음과 같은 점화식으로 구성된다.
\[up[k][v] = up[k-1][up[k-1][v]]\]즉, $v$의 $2^k$번째 조상은 $v$의 $2^{k-1}$번째 조상의 $2^{k-1}$번째 조상이다. $2^k = 2^{k-1} + 2^{k-1}$이므로 성립한다.
전처리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define LOG 17 // 2^17 = 131072 > 100000
int up[LOG][100001];
int depth[100001];
vector<int> adj[100001];
void dfs(int cur, int par, int d) {
up[0][cur] = par;
depth[cur] = d;
for (int nxt : adj[cur]) {
if (nxt == par) continue;
dfs(nxt, cur, d + 1);
}
}
void build(int n) {
for (int k = 1; k < LOG; k++) {
for (int v = 1; v <= n; v++) {
up[k][v] = up[k - 1][up[k - 1][v]];
}
}
}
dfs로 각 노드의 직속 부모(up[0][v])와 깊이를 구한 뒤, build에서 점화식을 통해 $2^k$번째 조상을 모두 채운다. 전처리의 시간복잡도는 $O(N \log N)$이다.
쿼리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int lca(int u, int v) {
// u가 더 깊도록 설정 후 깊이를 맞춘다.
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; k++) {
if ((diff >> k) & 1) {
u = up[k][u];
}
}
// 동시에 올라간다.
if (u == v) return u;
for (int k = LOG - 1; k >= 0; k--) {
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
}
return up[0][u];
}
깊이 차이 diff를 이진수로 분해하여, 해당 비트가 켜진 만큼 $2^k$칸 점프한다. 예를 들어 diff = 13 (1101₂)이면 $2^0$, $2^2$, $2^3$칸 점프하여 총 13칸을 올라간다.
이후 큰 $k$부터 시작하여, up[k][u] != up[k][v]인 경우에만 점프한다. LCA를 넘어가지 않는 가장 큰 점프만 수행하므로, 반복이 끝나면 $u$와 $v$는 LCA의 바로 아래 자식에 위치하게 된다. 따라서 up[0][u]가 LCA이다.
왜 up[k][u] == up[k][v]일 때 점프하지 않을까 ?
$2^k$번째 조상이 같다고 해서 그것이 LCA라는 보장이 없다. LCA보다 위에 있는 공통 조상일 수 있기 때문이다. 같지 않은 경우에만 점프하면, LCA를 넘어가지 않으면서 최대한 가까이 접근할 수 있다.
쿼리 하나의 시간복잡도는 $O(\log N)$이다. 전처리 $O(N \log N)$ 이후, $Q$개의 쿼리에 대해 $O(Q \log N)$의 시간복잡도를 가진다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#define LOG 17
int up[LOG][100001];
int depth[100001];
vector<int> adj[100001];
void dfs(int cur, int par, int d) {
up[0][cur] = par;
depth[cur] = d;
for (int nxt : adj[cur]) {
if (nxt == par) continue;
dfs(nxt, cur, d + 1);
}
}
void build(int n) {
for (int k = 1; k < LOG; k++) {
for (int v = 1; v <= n; v++) {
up[k][v] = up[k - 1][up[k - 1][v]];
}
}
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; k++) {
if ((diff >> k) & 1) {
u = up[k][u];
}
}
if (u == v) return u;
for (int k = LOG - 1; k >= 0; k--) {
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
}
return up[0][u];
}
시간복잡도 정리
| 기법 | 전처리 | 쿼리 | $Q$개 쿼리 전체 |
|---|---|---|---|
| Naive | $O(N)$ | $O(N)$ | $O(NQ)$ |
| Binary Lifting | $O(N \log N)$ | $O(\log N)$ | $O(N \log N + Q \log N)$ |