LCA (최소 공통 조상) 알고리즘

LCA 알고리즘이란?

2개의 노드가 주어질 경우, 해당 노드들의 공통된 조상 중 가장 깊이가 깊은 노드를 조회하는 알고리즘이다.

 

대략적인 순서는 다음과 같다.

 

1. 모든 노드에 대해 깊이를 계산한다.

2. 최소 공통 조상을 조회할 두개의 노드를 확인한다.

3. 해당 노드들의 깊이를 똑같이 맞춰준다.

4. 부모 노드를 한단계씩 거슬러 올라간다.

5. 하나의 노드에서 만날 때 나온 값 출력

 

코드는 다음과 같다. (백준 11437 문제 참고)

 

import sys

# 깊이 계산 함수
def dfs(node, depth):
    check_nod[node] = 1
    depth_nod[node] = depth

    for i in tree_nod[node]:
        if check_nod[i] == 1:
            continue
        parent_nod[i] = node
        dfs(i, depth + 1)

# lca 함수
def lca(x, y):
    # 노드 x와 y의 깊이를 맞춰주는 과정이 필요
    while depth_nod[x] != depth_nod[y]:
        if depth_nod[x] > depth_nod[y]:
            x = parent_nod[x]
        else:
            y = parent_nod[y]
    
    # 부모 노드 하나씩 거슬러 올라가는 과정
    while x != y:
        x = parent_nod[x]
        y = parent_nod[y]
    
    return x

n = int(input())
tree_nod = [[] for _ in range(n + 1)]
depth_nod = [0] * (n + 1)
parent_nod = [0] * (n + 1)
check_nod = [0] * (n + 1)

for i in range(n - 1):
    a, b = map(int, input().split())
    tree_nod[a].append(b) # a 인덱스에 해당하는 리스트에 b값 넣기 -> a와 b가 연결되어있음을 의미
    tree_nod[b].append(a)

dfs(1, 0)

m = int(input())
for i in range(m):
    x, y = map(int, input().split())
    ans = lca(x, y)
    print(ans)