소개

최소 공통 조상 문제는 트리의 임의의 두 정점의 조상 정점이면서 두 정점로부터의 거리가 가장 가까운 정점을 찾는 문제이다. 최소 공통 조상 문제는 트리 상의 임의의 두 정점의 경로를 탐색하는 데에 쓰일 수 있다.

해결

최소 공통 조상을 찾기 위해서 우리는 단순히 두 정점에서부터 출발해 만날때까지 하나씩 올라오는 방법을 생각해 볼 수 있다. 하지만 이 방법은 크기가 인 트리에서 의 시간복잡도를 가질 수 있어 적절하지 않다. 우리는 이 문제를 더 빠른 방법으로 해결해 볼 것이며 대표적으로 아래 두 방법이 존재한다.

다이나믹 프로그래밍

이 방식의 메인 아이디어는 조상 정점들을 탐색할 때 이분 탐색하듯이 거슬러 올라가도록 만드는 것이다. 우선 트리를 전처리한다. 트리 전체를 순회하면서 각 정점마다 깊이 정보와 함께 번째 조상 정점들을 저장해둘 것이다.

다이어그램을 그리는 중..

위 트리를 예시로 들어보자. 트리의 맨 아래 정점는 깊이가 5이고(루트의 깊이는 0이다) , , 번째 조상이 존재하므로 정점에 이 정보를 저장해 둔다. 모든 정점이 이러한 정보를 저장하고 있다면 최소 공통 조상 문제를 빠르게 풀 수 있다.

크기가 인 트리의 임의의 정점 와 의 최소 공통 조상 를 찾아가는 상황을 생각해보자. 트리는 위 예시처럼 전처리가 되어 있으며, 정점 의 깊이가 더 크고 정점 와 경로 사이에 정점 와 깊이가 같은 정점 이 있다고 하자. 도식화하면 아래 그림과 같으며 다른 정점는 생략하였다.

다이어그램을 그리는 중..

우선 정점 에서부터 정점 와 깊이가 같은 정점인 까지 거슬러 올라온다. 그러기 위해서 거슬러 올라가야 하는 거리인 를 구한다. 이는 간단히 정점 의 깊이에서 정점 의 깊이를 뺀 값이다. 예시로 이라고 해보자. 이는 다음과 같이 표현할 수 있다.

우리는 앞서 모든 정점의 번째 조상 정점을 구해놓았으므로 다음과 같은 경로로 정점 에서 정점 로 갈 수 있다.

다이어그램을 그리는 중..

즉, 정점 에서 정점 로 가는 데 의 시간이 든다. 이제 정점 과 에서 동시에 를 향해 올라온다. 거슬러 올라갈 조상 정점을 선택할 떄는 를 넘어서서 거슬러 올라가지 않으면서 가장 멀리 갈 수 있는 정점을 선택하면 된다. 이를 수학적으로 표현하면, 다음 집합의 최댓값 에 대해 번째 조상으로 계속해서 거슬러 올라가는 과정을 반복하면 된다.

번째 조상이 같지 않음

다이어그램을 그리는 중..

위 과정을 반복하면 최소 공통 조상인 정점 에서 만나게 될 것이다. 이 과정 역시 의 시간이 든다. 따라서 다이나믹 프로그래밍 기법을 사용한 최소 공통 조상 문제 풀이의 시간복잡도는 이다.

구현

아래는 최소 공통 조상의 다이나믹 프로그래밍적 접근을 코드화한 것이다. 각 정점마다 번째 조상을 저장하는 배열 root를 만들고 전처리 함수 preprocess를 통해 이를 채워둔다. 그리고 lca함수를 이용해 최소 공통 조상을 구한다.

 math  log2


 :
     :
         ():
            self.edge: [] = []  
            
            
            self.root: [] = []
            self.depth =   

        
         ():
             parent   :
                self.depth = parent.depth + 
                self.root.append(parent)
                now = parent
                t = 
                 t < (now.root):
                    now = now.root[t]
                    self.root.append(now)
                    t += 
             node  self.edge:
                 node   parent:
                    node.preprocess(self)

     ():
        self.node = [Tree.Node()  _  (size)]
         a, b  edge:
            a.edge.append(b)
            b.edge.append(a)
        
        self.node[root].preprocess()

    
     () -> Node:
        close, far = ([self.node[a], self.node[b]], key= x: x.depth)
        
        d = far.depth - close.depth
         i  ((log2(d)), -, -):
             d & ( << i):
                far = far.root[i]
        
         close != far:
            t = (far.root) - 
             t >   far.root[t] == close.root[t]:
                t -= 
            close, far = close.root[t], far.root[t]
         far

오일러 경로 테크닉

오일러 경로 테크닉이란 트리의 DFS 방문 순서대로 정점들을 나열하여 트리를 선형적으로 관리하는 기법이다. 오일러 경로 테크닉을 이용한 최소 공통 조상 문제의 풀이는 어떠한 정점 와 사이의 최소 공통 조상은 DFS 방문 순서상 정점 와 사이에서 반드시 재방문하게 됨을 이용한다.

최소 공통 조상 문제를 풀기 위해서는 정점에 번호를 매기는 방법을 조금 다르게 한다. 우선 빈 배열을 하나 생성한 뒤 DFS를 수행하면서 재방문을 포함해 정점에 방문할 때마다 해당 정점을 배열의 끝에 추가한다. 그리고 각 정점에는 깊이와 함께 배열에서 첫 번째와 마지막으로 등장하는 인덱스 번호를 저장한다. 아래 예시를 보자.

다이어그램을 그리는 중..

이 상황에서 정점 와 의 최소 공통 조상을 찾아보자. 배열 상에서 정점 나 가 처음 등장하는 인덱스는 3, 가장 마지막으로 등장하는 인덱스는 6이다. 따라서 인덱스 3과 6 사이에 있는 정점들 중에서 깊이가 가장 작은 정점인 가 이 두 정점의 최소 공통 조상이다.

다이어그램을 그리는 중..

이는 구간 최솟값 쿼리로 이해할 수 있으므로 세그먼트 트리를 사용하여 의 시간만에 문제를 해결할 수 있다.

구현

위 방법을 사용해 최소 공통 조상 문제를 푸는 알고리즘의 구현은 아래 코드 이외에도 다양하다. 아래 코드는 트리 클래스를 만들어 객체지향적인 구현을 한 것이다.

 :
     :
         ():
             r - l > :
                m = (l + r) // 
                self.left = SegmentTree.Node(array, l, m)
                self.right = SegmentTree.Node(array, m, r)
                self.value = (self.left.value, self.right.value)
            :
                self.value = array[l]

         () ->   :
             i <= l  r <= j:
                 self.value
              (r <= i  j <= l):
                m = (l + r) // 
                lv, rv = self.left.get_min(i, j, l, m), self.right.get_min(i, j, m, r)
                 lv  :
                     rv
                 rv  :
                     lv
                 (lv, rv)
            :
                 

    
     ():
        self.size = (array)
        self.root = SegmentTree.Node(array, , (array))

    
     () -> :
         self.root.get_min(i, j, , self.size)



 :
    
     :
         ():
            self.index = index
            self.edge: [] = []  
            self.depth =   
            self.in_num = 
            self.out_num = 
        
        
         ():
             self.depth < other.depth

        
         () -> []:
             parent   :
                self.depth = parent.depth + 
            self.in_num = num
            self.out_num = num + 
            array.append(self)
             node  self.edge:
                 node   parent:
                    node.euler_tour(array, self, self.out_num)  
                    array.append(self)
                    self.out_num = (array)
             array
    
    
     ():
        self.node = [Tree.Node(i)  i  (size)]
        self.segtree: SegmentTree   = 
         a, b  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())

    
     () -> :
         self.segtree.get_min(
            (self.node[a].in_num, self.node[b].in_num),
            (self.node[a].out_num, self.node[b].out_num)
        ).index

위 코드에서 Tree 클래스는 최소 공통 조상을 구할 트리를 나타낸다. preprocess 함수를 통해 오일러 경로 테크닉을 사용하여 배열을 만들고 세그먼트 트리를 구성한다. 그 후에 세그먼트 트리를 가지고 lca 함수로 들어오는 최소 공통 조상 쿼리를 처리한다.