소개
최소 공통 조상 문제는 트리의 임의의 두 정점의 조상 정점이면서 두 정점로부터의 거리가 가장 가까운 정점을 찾는 문제이다. 최소 공통 조상 문제는 트리 상의 임의의 두 정점의 경로를 탐색하는 데에 쓰일 수 있다.
해결
최소 공통 조상을 찾기 위해서 우리는 단순히 두 정점에서부터 출발해 만날때까지 하나씩 올라오는 방법을 생각해 볼 수 있다. 하지만 이 방법은 크기가
다이나믹 프로그래밍
이 방식의 메인 아이디어는 조상 정점들을 탐색할 때 이분 탐색하듯이 거슬러 올라가도록 만드는 것이다. 우선 트리를 전처리한다. 트리 전체를 순회하면서 각 정점마다 깊이 정보와 함께
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
위 트리를 예시로 들어보자. 트리의 맨 아래 정점는 깊이가 5이고(루트의 깊이는 0이다)
크기가
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
우선 정점
우리는 앞서 모든 정점의
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
즉, 정점
번째 조상이 같지 않음
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
위 과정을 반복하면 최소 공통 조상인 정점
구현
아래는 최소 공통 조상의 다이나믹 프로그래밍적 접근을 코드화한 것이다. 각 정점마다 root
를 만들고 전처리 함수 preprocess
를 통해 이를 채워둔다. 그리고 lca
함수를 이용해 최소 공통 조상을 구한다.
from math import log2
class Tree:
class Node:
def __init__(self):
self.edge: list['Tree.Node'] = [] # 간선으로 연결된 다른 정점들
# 2^n번째 조상을 저장하는 리스트
# 인덱스 i는 2^i번째 조상임을 의미
self.root: list['Tree.Node'] = []
self.depth = 0 # 정점의 깊이
# 전처리, 2^i번째 조상을 전부 구함
def preprocess(self, parent: 'Tree.Node' or None = None):
if parent is not None:
self.depth = parent.depth + 1
self.root.append(parent)
now = parent
t = 0
while t < len(now.root):
now = now.root[t]
self.root.append(now)
t += 1
for node in self.edge:
if node is not parent:
node.preprocess(self)
def __init__(self, size: int, root: int, edge: list[tuple[int, int]]):
self.node = [Tree.Node() for _ in range(size)]
for a, b in edge:
a.edge.append(b)
b.edge.append(a)
# 전처리
self.node[root].preprocess()
# 최소 공통 조상 구하기
def lca(self, a: int, b: int) -> Node:
close, far = sorted([self.node[a], self.node[b]], key=lambda x: x.depth)
# 더 깊이 있는 정점을 같은 깊이까지 끌어올린다
d = far.depth - close.depth
for i in range(int(log2(d)), -1, -1):
if d & (1 << i):
far = far.root[i]
# 두 정점로부터 최소 공통 조상까지 거슬러 올라온다
while close != far:
t = len(far.root) - 1
while t > 0 and far.root[t] == close.root[t]:
t -= 1
close, far = close.root[t], far.root[t]
return far
오일러 경로 테크닉
오일러 경로 테크닉이란 트리의 DFS 방문 순서대로 정점들을 나열하여 트리를 선형적으로 관리하는 기법이다. 오일러 경로 테크닉을 이용한 최소 공통 조상 문제의 풀이는 어떠한 정점
현재 블로그 개편의 일환으로 이미지를 저장하는 곳을 변경하고 있습니다. 개편이 완료될 동안 외부 리소스를 제외한 이미지는 표시되지 않습니다.
최소 공통 조상 문제를 풀기 위해서는 정점에 번호를 매기는 방법을 조금 다르게 한다. 우선 빈 배열을 하나 생성한 뒤 DFS를 수행하면서 재방문을 포함해 정점에 방문할 때마다 해당 정점을 배열의 끝에 추가한다. 그리고 각 정점에는 깊이와 함께 배열에서 첫 번째와 마지막으로 등장하는 인덱스 번호를 저장한다. 아래 예시를 보자.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
Depth | 0 | 1 | 1 | 1 | 2 | 2 | 3 |
indexstart | 0 | 1 | 9 | 11 | 2 | 6 | 3 |
indexend | 12 | 7 | 9 | 11 | 4 | 6 | 3 |
이 상황에서 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
이는 구간 최솟값 쿼리로 이해할 수 있으므로 세그먼트 트리를 사용하여
구현
위 방법을 사용해 최소 공통 조상 문제를 푸는 알고리즘의 구현은 아래 코드 이외에도 다양하다. 아래 코드는 트리 클래스를 만들어 객체지향적인 구현을 한 것이다.
# 구간 최솟값 쿼리를 지원하는 세그먼트 트리 (구현 편의를 위해 원소 갱신은 미지원)
class SegmentTree:
class Node:
def __init__(self, array: list[any], l: int, r: int):
if r - l > 1:
m = (l + r) // 2
self.left = SegmentTree.Node(array, l, m)
self.right = SegmentTree.Node(array, m, r)
self.value = min(self.left.value, self.right.value)
else:
self.value = array[l]
def get_min(self, i: int, j: int, l: int, r: int) -> any or None:
if i <= l and r <= j:
return self.value
elif not (r <= i or j <= l):
m = (l + r) // 2
lv, rv = self.left.get_min(i, j, l, m), self.right.get_min(i, j, m, r)
if lv is None:
return rv
if rv is None:
return lv
return min(lv, rv)
else:
return None
# 생성자
def __init__(self, array: list[any]):
self.size = len(array)
self.root = SegmentTree.Node(array, 0, len(array))
# 구간 최솟값 쿼리
def get_min(self, i: int, j: int) -> any:
return self.root.get_min(i, j, 0, self.size)
# 최소 공통 조상 쿼리를 지원하는 트리
class Tree:
# 트리의 정점
class Node:
def __init__(self, index: int):
self.index = index
self.edge: list['Tree.Node'] = [] # 간선으로 연결된 다른 정점들
self.depth = 0 # 정점의 깊이
self.in_num = 0
self.out_num = 0
# 정점 간의 대소 비교 정의, 이는 세그먼트 트리의 원소로서 사용하기 위함임
def __lt__(self, other: 'Tree.Node'):
return self.depth < other.depth
# 오일러 경로 테크닉으로 생성되는 리스트 반환
def euler_tour(self, array: list['Tree.Node'] = [], parent: 'Tree.Node' or None = None, num: int = 0) -> list['Tree.Node']:
if parent is not None:
self.depth = parent.depth + 1
self.in_num = num
self.out_num = num + 1
array.append(self)
for node in self.edge:
if node is not parent:
node.euler_tour(array, self, self.out_num) # 재귀
array.append(self)
self.out_num = len(array)
return array
# 생성자
def __init__(self, size: int, root: int, edge: list[tuple[int, int]]):
self.node = [Tree.Node(i) for i in range(size)]
self.segtree: SegmentTree or None = None
for a, b int edge:
self.node[a].edge.append(self.node[b])
self.node[b].edge.append(self.node[a])
# 전처리
self.segtree = SegmentTree(self.node[root].euler_tour())
# 최소 공통 조상
def lca(self, a: int, b: int) -> int:
return self.segtree.get_min(
min(self.node[a].in_num, self.node[b].in_num),
max(self.node[a].out_num, self.node[b].out_num)
).index
위 코드에서 Tree
클래스는 최소 공통 조상을 구할 트리를 나타낸다. preprocess
함수를 통해 오일러 경로 테크닉을 사용하여 배열을 만들고 세그먼트 트리를 구성한다. 그 후에 세그먼트 트리를 가지고 lca
함수로 들어오는 최소 공통 조상 쿼리를 처리한다.