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

1. 최소공통조상

LCA, Lowest common ancestor.

두 노드의 공통된 상위 부모노드(조상) 중에서, 가장 가까운 부모노드를 의미한다.

위 graph(tree)에서 8번노드와 15번노드의 LCA는 2번노드가 된다.

2. 해 도출 과정

• 모든 노드에 대한 깊이(루트노드로 부터 떨어진 길이)를 구한다.
  ※ 모든 노드에 대한 깊이는 DFS를 통해 도출한다.
• LCA를 찾을 두 노드를 확인하고, 두 노드의 깊이가 같아질때까지 계층을 올린다.
• 이후 부모가 같아질때까지 동일하게 계층을 올리는 작업을 반복한다.

구체적인 과정을 살펴본다면 아래와 같다.

• step 1

아래 노드 중 8과 15에 대한 LCA를 구한다고 해보자.

먼저, DFS를 이용해 모든 노드의 깊이를 구하고, LCA를 구하고자 하는 두 노드의 깊이를 확인한다.

• step 2

두 노드의 깊이를 맞춘다.

• step 3

두 노드의 공통된 부모노드(조상)을 만날때까지 거슬러 올라가는 과정을 반복한다.

3-1. 선형탐색을 통한 알고리즘 구현

기본적인 선형 탐색을 통해 LCA를 구하는 알고리즘 구현하면 다음과 같다.

단, 본 알고리즘은 매 쿼리(LCA 수행)마다 부모방향으로 거슬러 올라가기 위해 최악의 경우 O(N)의 시간복잡도가 요구되며 이에 따라 M번의 쿼리가 있다면 O(NM)까지 시간복잡도가 늘어난다.

#LCA, 최소공통조상

#N개의 정점으로 이루어진 트리가 주어진다.
#트리의 각 정점은 1번부터 N번까지 번호가 매겨져있고, 루트노드는 1번이다.
#두 노드의 쌍 M개가 주어져있을때, 두 노드의 가장 가까운 공통 조상을 구하는 알고리즘은?

import sys
n = int(sys.stdin.readline())

#1번 노드부터 각각의 부모노드를 기록할 배열 정보
parent = [0] * (n+1)
#각 노드의 깊이
#각 노드의 깊이가 계산되었는지의 여부
depth = [0] * (n+1)
isDepth = [False] * (n+1)
#graph 정보
graph = [[] * (n+1) for _ in range(n+1)]

for _ in range(n-1):
    #graph 정보
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

#dfs를 통해 모든 노드에 대해 깊이를 구한다.
def dfs(x, depth):
    isDepth[x] = True
    depth[x] = depth
    for y in graph[x]: #x노드에 대한 인접노드
        if isDepth[y]: #깊이 구했다면 continue
            continue
        parent[y] = x #하향탐색하는 과정으로, 부모노드의 정보를 입력
        dfs(y, depth+1)

#LCA
def lca(a,b):
    #두 노드의 depth를 동일하게 맞춘다
    while depth[a] != depth[b]:
        if depth[a] > depth[b]:
            a = parent[a]
        else:
            b = parent[b]

    #깊이를 같게 만든 후, lca를 본격적으로 찾는다.
    while a != b:
        #각 노드의 부모노드까지 거슬러 올라간다
        a = parent[a]
        b = parent[b]
        return a

#결과출력
dfs(1,0)

#반복횟수
m = sys.stdin.readline()
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(lca(a,b))

3-2. 개선된 형태의 LCA 알고리즘 구현

거슬러 올라가는 것을 2,4,8,16,...처럼 2의 거듭제곱 형태로 올라가는 단계를 늘리는 알고리즘을 말한다.
과정 자체는 동일하지만, 올라가는 형식을 2의 제곱씩 늘린다는 점에서 차이가 있고, 기존의 O(NM)시간복잡도를 O(MlogN)까지 줄일 수 있다.

다만 부모노드의 정보를 따로 기록해야 한다는 점에서 공간복잡도 측면에서는 불리하지만, 시간복잡도 측면에서는 훨씬 유리하므로 많이 사용한다.

• step 1

모든 노드의 깊이와 2^i 제곱 번째 부모에 대한 정보를 기록한다.

• step 2

이 이후의 과정은 기존 LCA과정과 동일하다(노드 깊이 구하고, 거슬러 올라간다).
다만, 거슬러 올라갈때 2^i 제곱만큼 올라간다.

#improved LCA

import sys
sys.setrecursionlimit(int(1e5)) #재귀함수 호출에러 해결
LOG = 21

n = int(input())
parent = [[0] * LOG for _ in range(n+1)] #부모노드 정보
d = [0] * (n+1) #노드깊이
c = [False] * (n+1) #노드깊이가 계산되었는지의 여부
graph = [[]*(n+1) for _ in range(n+1)] #각 노드의 인접노드 정보

for _ in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

#루트 노드로부터 시작하여 깊이를 구하는 함수
def dfs(x, depth):
    c[x] = True
    d[x] = depth
    for y in graph[x]:
        if c[y]:
            continue
        parent[y] = x
        dfs(y, depth+1)

#2의 제곱 형태로 거슬러 올라갈때의 부모노드 정보 기록
def setParent():
    dfs(1,0) #루트노드는 1번
    for i in range(1, LOG):
        for j in range(1, n+1):
            parent[j][i] = parent[parent[j][i-1]][i-1] #부모노드 기록

def lca(a,b):
    #b가 더 깊을 경우
    if d[a] > d[b]:
        a, b = b, a
    for i in range(LOG-1, -1, -1):
        if d[b] - d[a] >= (1 << i): #깊이차이가 충분히 클때 거슬러 올라간다
            b = parent[b][i]
        if a==b:
            return a #부모가 같아지도록
    for i in range(LOG-1, -1, -1):
        if parent[a][i] != parent[b][i]:
            a = parent[a][i]
            b = parent[b][i]
    return parent[a][0]

setParent()

m = int(input())

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(lca(a,b), end=' ')

4. 참조자료

이코테 2021 - LCA
https://www.youtube.com/watch?v=O895NbxirM8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=15