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

 

트리에서 두 노드 u, v의 가장 가까운 공통 조상을 찾는 알고리즘

💡공통 조상이란?

두 노드가 공통으로 공유하는 조상 노드의 집합

= 루트 노트에서 두 노드로 가는 경로가 만나는 노드의 집합

 

트리에서 LCA를 찾아보자!

        1
       / \
      2   3
     / \   \
    4   5   6
   / \
  8   9

• 2, 3의 LCA : 1
• 8, 5의 LCA : 2
• 4, 8의 LCA : 4

---

🔄 동작 원리

LCA를 찾는 일반적인 방법은 다음과 같습니다.

1. 깊이 맞추기 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 조상 방향으로 올려 깊이를 맞춥니다.
2. 공통 조상 찾기 두 노드가 같아질 때 까지 두 부모를 따라 올라가며 비교합니다.
3. 최종 공통 조상 반환 가장 먼저 발견된 공통 조상을 반환합니다.

1️⃣ 기본 방식

두 노드가 깊이가 다른 경우 깊이가 더 깊은 노드는 부모를 하나씩 따라 올라가며 깊이를 맞춥니다.

이후 두 노드는 공통 조상을 찾기 위해 부모를 하나씩 따라 올라가며 공통 조상을 찾습니다.

시간복잡도

• DFS 전처리 : O(N)
• LCA 쿼리 : O(QN)

= O(N + QN) =(QN)

2️⃣ 희소 배열을 이용한 빠른 LCA 탐색

기본 방식과 동작 원리는 동일하나, 두 노드의 깊이를 맞추고, 공통 조상을 찾는 과정에서 희소배열을 사용하여 $2^i$만큼 올라갑니다.

시간복잡도

• DFS, 희소배열 전처리 : O(NlogN)
• LCA 쿼리 : O(QlogN)

= O(NlogN + QlogN) = O((N + Q)logN)

 

 

---

🏗️ 구현

📜N개의 노드에 대한 N - 1개 연결된 두 정점의 쌍이 주어지며, 노드의 번호는 1 ~ N입니다.

두 노드 u, v에 대해 LCA를 찾아야 하며, Q개의 LCA 쿼리가 주어집니다.

기본 방식

1. 트리 구성

모든 정점의 깊이를 계산하고, 조상 노드를 찾기 위해 무방향 트리를 구성해야 합니다.

from collections import defaultdict

tree = defaultdict(list)

for _ in range(N - 1):
    u, v = map(int, input().split())
    tree[u].addend(v)
    tree[v].append(u)

parent = [0] * (N + 1)
depth = [0] * (N + 1)

2. DFS 전처리

이후 DFS를 통해 현재 노드의 깊이와 부모 노드의 정보를 저장합니다.

def dfs(node, _parent):
    parent[cur] = _parent
    depth[cur] = depath[_parent] + 1
    for child in tree[cur]:
        if child != _parent:
            dfs(child, cur)

3. LCA 탐색

이제 LCA를 탐색할 순서입니다.

우선 두 노드 u, v의 깊이가 다른 경우 깊이가 깊은 노드를 깊이가 얕은 노드와 깊이가 동일하도록 부모 노드를 반복해서 찾습니다.

def lca():
    while depth[u] > depth[v]:
        u = parent[u]
    while depth[v] > depth[u]:
        v = parent[v]

이후, 깊이가 동일한 두 정점 u, v에 대해 공통 조상을 찾습니다.

    while u != v:
        u = parent[u]
        v = parent[v]
    return u

 

---

✏️연습 문제

부모-자식 관계를 알고 있을 때

https://www.acmicpc.net/problem/11437

기본 예제(관계를 모를 때)

https://www.acmicpc.net/problem/11437

 

 

 

 

---

💪 확장

희소 배열을 이용한 빠른 탐색

기존에는 parent배열에 부모 노드의 정보를 기록하고, 선형 탐색으로 LCA를 탐색했습니다.

이러한 방식은 구현이 단순하지만, 노드의 깊이가 깊어지거나, 질의의 수가 많아질 경우 비효율적입니다.

1. 트리 구성

기본적인 전처리, 탐색로직은 기존과 유사하지만, 희소배열 전처리와 LCA를 탐색하는 과정에서 parent를 사용하는 방법이 변경됩니다.

parent[i][j] # 정점 i의 2^j번째 조상 정점 

우선, 현재 노드의 부모 노드를 기록하던 parent를 $2^k$번째 조상 노드까지 기록하기 위해 $logN$만큼 parent를 2차원 배열로 확장해야 합니다.

MAX_DEPTH = int(log2(N))
parent = [[0] * (MAX_DEPTH + 1) for _ in range(N + 1)]

2. DFS 및 희소배열 전처리

DFS를 하며 깊이와 부모노드(parent[cur][0])을 기록할 뿐 아니라 조상 노드까지 기록합니다.

def dfs(cur, _parent):
    depth[cur] = depth[_parent] + 1

    # 희소배열 전처리
    parent[cur][0] = _parent
    for j in range(1, MAX_DEPTH + 1):
        parent[cur][k] = parent[parent[cur][j - 1]][j - 1]
    for child in tree[cur]:
        if child != _parent:
            dfs(child, cur)

3. LCA 탐색

희소 배열을 사용한 LCA 탐색은 조상 노드를 건너뛸 수 있습니다.

따라서, 두 정점의 깊이를 맞추는 과정을 다음과 같이 변경할 수 있습니다.

def lca(u, v):
    if depth[u] < depth[v]:
        u, v = v, u
    for j in range(MAX_DEPTH, -1, -1):
        if depth[parent[u][j]] >= depth[v]:
            u = parent[u][j]

노드의 깊이를 맞춘 후 LCA라면 반환을, 아니라면 희소 배열을 사용해 LCA를 찾아서 반환합니다.

    if u == v:
        return u
    for j in range(MAX_DEPTH, -1, -1):
        if parent[u][j] != parent[v][j]:
            u = parent[u][j]
            v = parent[v][j]
    return parent[u][0]

 

---

✏️연습 문제

기본 예제(쿼리가 많을 때)

https://www.acmicpc.net/problem/11438

두 정점 간의 거리

https://www.acmicpc.net/problem/1761