소개
트리는 비선형 자료구조다. 비선형이라고 함은 적어도 2차원 상에서 생각해야 한다는 것이다. 오일러 경로 테크닉은 비선형 자료구조인 트리를 다루기 쉬운 선형 자료구조로 환원하는 방법을 제시한다. 오일러 경로 테크닉이라고 해서 오일러 경로에 대한 정의나 오일러 경로를 구하는 알고리즘을 알 필요는 없다.
원리
오일러 경로 테크닉은 쉽게 말해서 DFS로 정점에 순서를 부여하고 그 순서대로 나열하는 것이다. 아래 트리를 오일러 경로 테크닉을 통해 정점에 순서를 부여해보자.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
현재 블로그 개편의 일환으로 이미지를 저장하는 곳을 변경하고 있습니다. 개편이 완료될 동안 외부 리소스를 제외한 이미지는 표시되지 않습니다.
위 트리를 옆의 그림과 같이 DFS 방식으로 순회하면서 각 정점에 총 두 개의 번호
0 | 1 | 5 | 6 | 2 | 4 | 3 | |
7 | 5 | 6 | 7 | 4 | 5 | 4 |
정점들을
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
오일러 경로 테크닉은 다시 해석하면 서브 트리들의 모든 정점들을 배열의 인접한 구간에 위치하도록 하는 것이다. 이렇게 만들면 서브 트리 및 조상 정점와 후손 정점 사이에 대한 쿼리를 세그먼트 트리 등을 적용해 쉽게 풀 수 있다.
응용
후손까지 경로 찾기
트리의 어떤 정점에서부터 임의의 후손 정점까지의 경로를 찾아야 한다고 해보자. 후손 정점까지 가려면 수많은 자식 정점을 선택하면서 전진해야 할 것이다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
전진할 자식 정점을 선택하려면 자식 정점들의
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
각 정점 안에서는 자식 정점들이
최소 공통 조상
최소 공통 조상 문제는 트리의 어떠한 두 정점이 주어지면 해당 정점들의 가장 가까운 공통 조상을 찾는 문제이다. 이 문제는 오일러 경로 테크닉을 사용하여
서브 트리에 대한 쿼리
각 정점이 가중치를 지니고 있는 트리가 있다. 이 트리에서 다음과 같은 문제를 정의할 수 있다.
다음 쿼리를 처리하는 프로그램을 작성하라.
set x v
: 정점x
를 루트로 하는 서브 트리의 모든 정점의 가중치에v
를 더한다.print x
: 정점x
의 가중치를 출력한다.
1번 쿼리를 DFS로 해결하려 할 경우 매 쿼리마다
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
구현
오일러 경로 테크닉은 결국 단순 DFS의 결과이므로 구현이 어렵지 않다. 아래 코드는 정점 객체에 오일러 경로 테크닉 함수를 구현한 것이다.
class Node:
def __init__(self):
self.edge: list['Node'] = [] # 간선으로 연결된 다른 정점들
self.in_num = 0
self.out_num = 0
# 오일러 경로 테크닉으로 생성되는 리스트 반환
def euler_tour(self, array: list['Node'] = [], parent: 'Node' or None = None, num: int = 0) -> list['Node']:
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) # 재귀
self.out_num = node.out_num
return array
# 두 정점의 연결
def connect(a: Node, b: Node):
a.edge.append(b)
b.edge.append(a)
루트 정점의 euler_tour
함수를 호출하면 트리의 모든 정점의 in_num
과 out_num
이 계산되며 그로 인해 만들어지는 배열이 반환된다. 이 배열을 이용해 최소 공통 조상을 구하거나 서브 트리에 대한 쿼리를 처리하는 알고리즘을 구현하는 것은 독자의 몫이다.