Quick Flow
| 항목 | 내용 |
|---|---|
| 대상 | 루트가 정해진 트리 |
| 질문 | 두 정점의 가장 가까운 공통 조상 |
| 전처리 | 부모·깊이·점프 표 O(N log N) |
| binary lifting | up[k][v]: v의 2^k번째 조상 |
| 질의 | O(log N) |
csharp
int LOG = 1;
while ((1L << LOG) <= n) LOG++;
int[,] up = new int[LOG, n];
int[] depth = new int[n];루트가 고정되고 LCA 질의가 많으면 binary lifting을 전처리합니다. 질의가 한두 번뿐이면 부모를 따라 올리는 단순 방법이 더 가볍습니다.
구조
LCA는 두 정점을 같은 깊이로 맞춘 뒤, 동시에 위로 올려 가장 가까운 공통 조상을 찾습니다. 부모를 한 칸씩만 따라가면 질의마다 O(N)이 걸릴 수 있으므로, 많은 질의에서는 binary lifting을 씁니다.
text
up[0][v] = v의 부모
up[1][v] = v의 2번째 조상
up[2][v] = v의 4번째 조상전처리는 DFS나 BFS로 깊이와 직계 부모를 채운 뒤, 점화식으로 위쪽 조상을 계산합니다.
csharp
sealed class LowestCommonAncestor
{
private readonly int[,] up;
private readonly int[] depth;
private readonly int log;
public LowestCommonAncestor(IReadOnlyList<int>[] tree, int root = 0)
{
int n = tree.Length;
if (n == 0 || (uint)root >= (uint)n)
{
throw new ArgumentOutOfRangeException(nameof(root));
}
log = 1;
while ((1L << log) <= n) log++;
up = new int[log, n];
depth = new int[n];
var visited = new bool[n];
var queue = new Queue<int>();
visited[root] = true;
up[0, root] = root;
queue.Enqueue(root);
while (queue.Count > 0)
{
int current = queue.Dequeue();
foreach (int next in tree[current])
{
if (visited[next]) continue;
visited[next] = true;
depth[next] = depth[current] + 1;
up[0, next] = current;
queue.Enqueue(next);
}
}
for (int v = 0; v < n; v++)
{
if (!visited[v]) throw new ArgumentException("루트에서 닿지 않는 정점이 있습니다.", nameof(tree));
}
for (int k = 1; k < log; k++)
{
for (int v = 0; v < n; v++)
{
up[k, v] = up[k - 1, up[k - 1, v]];
}
}
}
public int Query(int a, int b)
{
if ((uint)a >= (uint)depth.Length || (uint)b >= (uint)depth.Length)
{
throw new ArgumentOutOfRangeException();
}
if (depth[a] < depth[b]) (a, b) = (b, a);
int diff = depth[a] - depth[b];
for (int k = 0; k < log; k++)
{
if (((diff >> k) & 1) == 1) a = up[k, a];
}
if (a == b) return a;
for (int k = log - 1; k >= 0; k--)
{
if (up[k, a] == up[k, b]) continue;
a = up[k, a];
b = up[k, b];
}
return up[0, a];
}
}부모가 없는 루트는 자기 자신을 부모로 두면 경계 처리가 단순해집니다. 위 구현은 root에서 닿는 하나의 트리를 전제로 하며, 양방향 인접 리스트를 넣을 때 visited가 부모 방향 재방문을 막습니다.
질의 흐름
Query(a, b)는 먼저 더 깊은 정점을 위로 올려 두 정점의 깊이를 맞춥니다. 이때 둘이 같아지면 그 정점이 LCA입니다. 다르면 큰 점프부터 보면서 조상이 달라지는 마지막 지점까지 함께 올리고, 그 직계 부모를 반환합니다.
주의할 점
LOG는 2^LOG가 정점 수 이상이 되도록 잡아야 합니다. 고정값을 쓰면 입력 제한이 바뀌는 순간 가장 높은 조상 점프를 잃을 수 있으므로, 정점 수에서 동적으로 계산하는 편이 안전합니다.
LCA는 트리 기준입니다. 일반 그래프에서는 먼저 루트 트리, BFS 트리, DFS 트리처럼 어떤 트리 위의 조상을 묻는지 정의해야 합니다.
참고 링크
1 sources