최소 공통 조상

• 최소 공통 조상(LCA; Lowest Common Ancestor) 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제이다.

방법

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

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

import sys
sys.setrecursionlimit(int(1e5))

n = int(input())

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):                 # 루트 노드로부터 시작하여 깊이(depth)을 구하는 함수(DFS)
	c[x] = True
	d[x] = depth
	for y in graph[x]:
		if (not c[y]):
			parent[y]=x
			dfs(y,depth+1)

def lca(a, b):                     # a,b의 최소 공통 조상을 찾는 함수
		while d[a]!=d[b]:              # a,b의 깊이(depth)가 동일하도록 거슬러 올라간다.
			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번 노드, 깊이 0부터 시작하여 깊이 계산

m = int(input())

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

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

개선된 최소 공통 조상 알고리즘

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e5))
LOG = 21

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):                         # 루트 노드로부터 시작하여 깊이를 구하는 함수 (DFS)
	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():                                  # 전체 부모 관계를 설정하는 함수
	dfs(1,0)
	for i in range(1,LOG):
		for j in range(1,n+1):
			parent[j][i] = parent[parent[j][i-1]][i-1]   # parent[i][j] : 정점 i의 2^j번째 조상
																									 # parent[i][j] = parent[parent[i][j-1]][j-1]
                                                   # 즉 정점 i의 2^j번째 조상은 i의 [2^(j-1)번째 조상]의 2^(j-1)번째 조상과 동일함

def lca(a, b):
	if d[a]>d[b]: a,b=b,a                            # 항상 b의 깊이가 더 크도록 설정
	for i in range(LOG-1, -1,-1):
		if d[b]-d[a]>=(1<<i):                          # 깊이 차이가 2^i 보다 크다면 b를 끌어올림
			b=parent[b][i]
	if a==b:                                         # a와 b가 같아졌다면 그대로 리턴
		return a
	for i in range(LOG-1, -1, -1):                   # a의 부모와 b의 부모가 같아질 때까지 최대 크기부터 끌어올림
		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 _ in range(m):
		a, b = map(int, input().split())
		print(lca(a,b))

• 각 노드가 거슬러 올라가는 속도를 빠르게 만드는 방법이 필요하다.
• 2의 제곱 형태로 거슬러 올라가도록 하면 O(logN)의 시간 복잡도를 보장할 수 있다.
  • 15칸을 올라가고자 할 때 8칸 → 4칸 → 2칸 → 1칸 이동하면 4번만에 도달 가능
• 메모리를 조금 더 사용하여 각 노드에 대해 2^i번째 부모에 대한 정보를 기록한다.