최소 공통 조상 (LCA, Lowest Common Ancestor)

구현 코드 예시

from collections import deque

LOG = 18                              # 2^18 = 262144 > 10만. n에 맞춰 잡는다


def build(n, graph, root=1):
    up = [[0] * (n + 1) for _ in range(LOG)]
    depth = [0] * (n + 1)

    visited = [False] * (n + 1)       # BFS로 부모와 깊이를 채운다 (재귀 깊이 걱정 없음)
    visited[root] = True
    q = deque([root])
    while q:
        v = q.popleft()
        for nxt in graph[v]:
            if not visited[nxt]:
                visited[nxt] = True
                up[0][nxt] = v
                depth[nxt] = depth[v] + 1
                q.append(nxt)

    for k in range(1, LOG):           # 절반짜리 점프를 두 번 이어 두 배 점프를 만든다
        for v in range(1, n + 1):
            up[k][v] = up[k - 1][up[k - 1][v]]

    return up, depth


def lca(a, b, up, depth):
    if depth[a] < depth[b]:           # a를 항상 더 깊은 쪽으로
        a, b = b, a

    diff = depth[a] - depth[b]
    for k in range(LOG):              # 깊이 차이를 이진수로 쪼개 점프
        if diff & (1 << k):
            a = up[k][a]

    if a == b:                        # 한쪽이 다른 쪽의 조상이었던 경우
        return a

    for k in range(LOG - 1, -1, -1):  # 큰 점프부터, 조상이 다를 때만 올라간다
        if up[k][a] != up[k][b]:
            a = up[k][a]
            b = up[k][b]

    return up[0][a]                   # 갈라지기 직전에 멈췄으므로 부모가 답


def distance(a, b, up, depth):
    """트리에서 두 노드 사이의 간선 개수."""
    return depth[a] + depth[b] - 2 * depth[lca(a, b, up, depth)]

두 번째 반복문에서 큰 점프부터 시도하는 것이 중요하다. 작은 것부터 하면 LCA를 지나칠 수 있다. 그리고 up[k][a] != up[k][b]일 때만 올라가므로, 절대 LCA를 넘어가지 않고 정확히 그 아래에서 멈춘다.

루트의 부모를 0으로 두고 up[k][0] = 0이 되게 하면, 범위를 벗어난 점프가 0에 머물러 자동으로 안전해진다. 정점 번호를 1부터 쓰는 이유가 이것이다.

LCA로 풀리는 문제들

• 두 노드 사이의 거리: depth[a] + depth[b] - 2 × depth[lca]. 위 코드의 distance가 그것이다.
• 경로가 특정 노드를 지나는가: lca(a, b)가 그 노드이거나, 그 노드가 경로 위에 있는지 깊이로 판별한다.
• 경로 위의 최댓값·합: up과 같은 방식으로 maxval[k][v]를 함께 만들어두면 점프하면서 동시에 집계할 수 있다.
• 트리에서의 k번째 조상: LCA를 구할 필요 없이 깊이 맞추기 로직만 떼어 쓰면 된다.

자주 하는 실수

• 깊이를 맞추지 않고 같이 올라간다. 서로 다른 층에 있으면 만나는 지점이 공통 조상이라는 보장이 없다.
• 두 번째 단계에서 작은 점프부터 한다. 반드시 range(LOG - 1, -1, -1)로 큰 것부터다. 작은 것부터 하면 LCA를 지나쳐 루트까지 올라가 버린다.
• a == b 검사를 빼먹는다. 한 노드가 다른 노드의 조상인 경우, 깊이를 맞춘 직후 둘이 같아진다. 이때 바로 반환하지 않으면 두 번째 반복문이 엉뚱한 답을 낸다.
• LOG를 너무 작게 잡는다. 2^LOG가 최대 깊이보다 커야 한다. n이 10만이면 17 이상, 넉넉히 20으로 잡으면 안전하다.
• DFS 재귀로 부모를 채운다. 일자로 늘어진 트리에서 재귀 깊이 초과가 난다. BFS를 쓰거나 재귀 한도를 올린다.
• 희소 배열 채우는 순서를 뒤집는다. k 바깥, v 안쪽이어야 한다. up[k]는 up[k-1]이 모두 채워진 뒤에야 계산할 수 있다.

면접에서 이렇게 물어본다

• LCA가 무엇이고 어떤 문제에 쓰이는지 설명해 보라.
• 단순한 방법의 복잡도와 그것이 부족한 상황은 언제인가.
• up[k][v] = up[k-1][up[k-1][v]]가 성립하는 이유를 설명해 보라.
• 희소 배열로 질의가 O(log n)이 되는 이유는 무엇인가.
• 갈라지는 지점을 찾을 때 큰 점프부터 시도해야 하는 이유는 무엇인가.
• 트리에서 두 노드 사이의 거리를 LCA로 어떻게 구하는가.
• 전처리 비용과 질의 비용의 트레이드오프를 어떻게 판단하겠는가.