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

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

• 최소 공통 조상(LCA): 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제

여기서 3번 노드와 11번 노드의 공통 조상 노드는 1번이다.

 

✔️ 동작 과정

1. 모든 노드에 대한 깊이(depth)를 계산
2. 최소 공통 조상을 찾을 두 노드를 확인
   1. 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다.
   2. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다.
3. 모든 LCA(a, b) 연산에 대하여 2번의 과정을 반복한다.

 

1) 모든 노드 깊이 계산

 

우선 DFS를 이용해서 루트 노드에서부터의 깊이를 구한다.

 

2) 공통 조상을 구할 노드 선택

 

두 노드의 깊이를 맞춰주고, 거슬러 올라간다.

그렇게 2번 노드가 공통 조상임을 찾을 수 있다!

 

✔️ 소스 코드 구현 (Python) 

1️⃣ 기본적인 최소 공통 조상 알고리즘

import sys
sys.setrecursionlimit(int(1e5)) # 런타임 오류 피하기. 재귀 깊이 제한.

n = int(input())

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

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

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

# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
    # 먼저 깊이(depth)가 동일하도록
    while d[a] != d[b]:
        if d[a] > d[b]:
            a = parent[a]
        else:
            b = parent[b]
    # 노드가 같아지도록
    while a != b:
        a = parent[a]
        b = parent[b]
    return a

dfs(1, 0) # 루트 노드는 1번 노드

m = int(input())

for i in range(m):
    a, b = map(int, input().split())
    print(lca(a, b))

 

 

[ A와 B의 최소 공통 조상을 찾는 함수 ]

 

함수에 들어온 노드 a와 노드 b의 깊이를 가지고 있는 d 리스트에서 값을 비교해 보고

만약 a가 깊이가 더 깊다면 parent 리스트에서 a의 부모 노드로 이동하도록 바꿔준다.

바뀐 노드와 기존 노드를 비교하고 깊이가 같아지면 종료한다.

 

깊이를 맞춰준 다음 a노드와 b노드가 같아질 때까지 부모 노드로 이동한다.

 

def lca(a, b):
    # 먼저 깊이(depth)가 동일하도록
    while d[a] != d[b]:
        if d[a] > d[b]:
            a = parent[a]
        else:
            b = parent[b]
    # 노드가 같아지도록
    while a != b:
        a = parent[a]
        b = parent[b]
    return a

 

 

[ 시간 복잡도 ]

 

• 매 쿼리마다 부모 방향으로 거슬러 올라가기 위해 최악의 경우 O(N)의 시간 복잡도가 요구된다.
  • 따라서 모든 쿼리를 처리할 때의 시간 복잡도는 O(NM)

 

백준의 11437번 LCA를 위 방법으로 풀었더니 시간초과가 났다 ㅠㅠ

 

 

2️⃣  개선된 구현 방법

각 노드가 거슬러 올라가는 속도를 빠르게 만드는 방법으로 해결

 

import sys
input = sys.stdin.readline # 시간 초과를 피하기 위한 빠른 입력 함수
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정
LOG = 21 # 2^20 = 1,000,000

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

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

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

# 전체 부모 관계를 설정하는 함수
def set_parent():
    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]

# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
    # b가 더 깊도록 설정
    if d[a] > d[b]:
        a, b = b, a
    # 먼저 깊이(depth)가 동일하도록
    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]

set_parent()

m = int(input())

for i in range(m):
    a, b = map(int, input().split())
    print(lca(a, b))

 

• 2의 제곱 형태로 거슬러 올라가도록 하여 O(logN) 시간복잡도 보장
  • 8칸 -> 4칸 -> 2칸 -> 1칸

즉, 메모리를 좀 더 할당해서 각 노드에 대하여 2^i 번째 부모에 대한 정보를 기록한다.

 

 

[ 알고리즘 풀이 ]

 

예를 들어 노드 15에 대한 부모의 정보는 i=0일 때는 2^0. 즉 1번째 위에 있는 노드 11을 저장하고,

i=1일 때는 2^1. 2번째 위에 있는 노드 5. i=2일 때에는 2^2. 4번째 위에 있는 노드 1을 저장한다.

 

기존에는 한 칸씩 부모 노드를 찾으러 올라갔다면 이제는 2^i씩 거슬러 올라가서 최소 조상 노드를 찾아낸다.

 

그래서 1, 2, 4, 8, 16번째 떨어진 부모들을 찾아야 한다.

 

1) 기존 코드와 동일하게 각 노드의 깊이를 구한다.

 

기존 코드와 다른 점은 parent 리스트가 2차원 배열이고 parent[y]가 노드 y의 부모 노드를 가진 리스트이고

이 리스트의 0번째로 1번째 떨어진 부모의 노드를 넣는다.

def dfs(x, depth):
    c[x] = True
    d[x] = depth
    for y in graph[x]:
        if not c[y]:
            parent[y][0] = x
        	dfs(y, depth + 1)

 

 

2) 전체 부모 노드를 찾는다.

 

지금은 1번째 떨어진 부모만 있기 때문에 2, 4, 8 ... 떨어진 부모를 찾아보자.

 

아래 parent[j][i] = parent[parent[j][i - 1]][i - 1] 이 부분 이해가 참 어려웠는데 ㅠㅠ 천천히 알아보자.

 

쉽게 생각하면 2번째 떨어진 부모는 1번째 떨어진 부모의 1번째 떨어진 부모이다.

4번째 떨어진 부모는 2번째 떨어진 부모의 2번째 떨어진 부모이다.

 

정리하면, 

 

- current 노드의 1, 2, 4, 8, 16, .... 떨어진 부모를 찾아서 리스트로 가지고 있어야 한다.

- 1번째 떨어진 부모는 dfs()로 깊이를 구할 때 넣어줬다.

- 2번째 떨어진 부모를 찾기 위해서는 부모 리스트에서 1번째 떨어진 부모로부터 1번째 떨어진 부모이다.

- 4번째 떨어진 부모를 찾기 위해서는 부모 리스트에서 2번째 떨어진 부모로부터 2번째 떨어진 부모이다.

 

우와 너무 말장난같아 어질어질

 

def set_parent():
    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]

 

 

3) 최소 공통 조상 구하기

 

우선 b가 항상 깊도록 만들어 준다.

그다음 노드 a와 노드 b의 깊이 차이를 확인하여 충분히 차이가 크다면 2의 제곱으로 줄어들게 해서 깊이를 맞춘다.

 

예를 들어 깊이 15라면 8, 4, 2, 1 순으로 줄어든다.

 

그다음 노드가 같아질 때까지 부모를 찾아 올라간다.

def lca(a, b):
    # b가 더 깊도록 설정
    if d[a] > d[b]:
        a, b = b, a
    # 먼저 깊이(depth)가 동일하도록
    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]

 

 

 

[ 시간 복잡도 ]

 

• 다이나믹 프로그래밍(DP)을 이용해 시간 복잡도를 개선할 수 있다.
  • 세그먼트 트리를 이용하는 방법도 존재
• 매 쿼리마다 부모를 거슬러 올라가기 위해 O(logN)의 복잡도 필요
  • 모든 쿼리를 처리할 때의 시간 복잡도는 O(MlogN)

 

---

📌 Reference & Additional Resources

• [한빛미디어] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)
• https://kibbomi.tistory.com/201