[알고리즘] 최소 공통 조상 (LCA, Lowest Common Ancestor)

kimgwon·2024년 10월 29일

Algorithm

목록 보기

14/15

최소 공통 조상

두 노드의 공통된 조상 중 가장 가까운 조상을 찾는 문제이다.

기초 문제

BOJ 'LCA' 문제 中
N(2 <= N <= 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 <= M <= 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

알고리즘

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

DFS 이용한 깊이 계산

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

import sys
sys.setrecursionlimit(int(1e5)) # 런타임 오류 피하기 위해

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

for _ in range(n - 1):
	a, b = map(int, input().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)
     
# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
	# 먼저 깊이가 동일하도록
	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
    
# 루트 노드는 1번 노드
dfs(1, 0)

m = int(input())

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

심화 문제

BOJ 'LCA 2' 문제 中
N(2 <= N <= 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져있으며, 루트는 1번이다. 두 노드의 쌍 M(1 <= M <= 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

알고리즘 개선

각 노드가 거슬러 올라가는 속도를 빠르게 만들면 된다.
만약 총 15칸을 거슬러 올라가야 한다면, 8 -> 4 -> 2-> 1 형태로 거슬러 올라가게끔 한다.
2의 제곱 형태로 거슬러 올라가도록 하면 O(logN)의 시간 복잡도를 보장한다.
따라서, 각 노드에 대하여 $2^i$ 번 째 부모에 대한 정보를 기록하자.

DP 이용한 깊이 계산

매 쿼리마다 부모를 거슬럴 올라가기 위해 O(logN)의 시간 복잡도가 필요하다.
따라서 모든 쿼리를 처리할 때의 시간 복잡도는 O(MlogN)이다.

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

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

for _ in range(n - 1):
	a, b = map(int, input().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][0] = x
        dfs(y, depth + 1)
        
# 전체 부모 관계를 설정하는 함수
def set_parent():
	# 루트 노드는 1번 노드
	dfs(1, 0)
    for i in range(1, LOG):
    	for i 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
    # 먼저 깊이가 동일하도록
    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))