최소 공통 조상(LCA) 구현 톺아보기 - 2

최소 공통 조상 구현 톺아보기 목록

1. 부모를 따르는 시뮬레이션
2. 깊이 우선 탐색의 순서
3. 구간 최솟값 질의

이번 글에서는 깊이 우선 탐색^{Depth First Search}의 방문 순서를 이용해서 최소 공통 조상을 구하는 알고리즘을 알아보려고 합니다. 이 알고리즘들은 문제 해결 분야에서 잘 알려지지 않았지만 효율적이고, 문제에 따라 구현이 간단한 경우도 있으므로 알아두시면 좋을 것 같습니다. 트리에서 깊이 우선 탐색은 $\mathcal{O}(V)$ 시간이 걸리므로 최소 공통 조상을 구할 때마다 시행하기는 어렵고, 한 번의 깊이 우선 탐색에서 정점 $Q$쌍의 최소 공통 조상을 모두 구하는 방식을 사용합니다.

본격적인 알고리즘을 설명하기 전에, 최소 공통 조상과 관련된 깊이 우선 탐색의 특징을 설명하려고 합니다. 깊이 우선 탐색에서 모든 정점은 방문 시작 시기와 종료 시기가 있습니다. 부모 정점에서(혹은 깊이 우선 탐색 시작 시에) 다음 정점으로 이동할 때가 방문 시작이고, 현재 정점에서 부모 정점으로(혹은 깊이 우선 탐색의 종료로) 이동할 때가 방문 종료입니다. 깊이 우선 탐색 시에, 어떤 두 정점 A와 B, 그리고 두 정점의 최소 공통 조상 C가 어떤 순서로 방문되는지를 살펴보겠습니다. 크게 두 가지 경우로 나눌 수 있습니다.

• A = C인 경우. B = C인 경우도 마찬가지입니다.

  A의 방문 시작 및 C의 방문 시작 → B의 방문 시작 → B의 방문 종료 → A의 방문 종료 및 C의 방문 종료

• A ≠ C이고 B ≠ C인 경우.

  C의 방문 시작 → A의 방문 시작 → A의 방문 종료 → B의 방문 시작 → B의 방문 종료 → C의 방문 종료

두 경우 모두 C를 방문 시작하고, A, B를 방문 종료한 뒤 C를 방문 종료하게 됩니다. 이 조건을 처음 만족하는 정점이 최소 공통 조상이라는 사실 또할 알 수 있으므로, 방문 순서를 이용하여 최소 공통 조상을 찾을 수 있습니다.

자식 집합과 부모 집합을 합치기

각 정점마다 처리해야 할 최소 공통 조상 질의의 번호를 저장하는 집합을 저장해 두겠습니다. 정점의 방문이 끝날 때마다, 부모 정점의 집합에 자식 정점의 집합을 합칩니다. 이때 두 집합에 공통 원소가 있다면, 부모 정점이 두 정점 A, B의 조상이면서 가장 처음으로 방문 종료하게 되는 조상이 되므로 최소 공통 조상임을 알 수 있습니다. 공통된 번호의 질의에 부모 정점을 답하면 됩니다.

공통 원소 확인은 집합을 합치는 과정에서 수행할 수 있으므로 집합을 합치는 시간만 고려해도 충분합니다. 일자형 그래프에서 가장 깊은 정점은 $V-1$번, 그다음으로 깊은 정점은 $V-2$번, …, 복사가 잍어나고 루트까지 집합을 합치는 데에는 $\mathcal{O}(Q^2)$회의 복사가 필요합니다.

글의 처음에서 효율적이라 했는데 제곱 시간이 걸려 의아하실지도 모르겠습니다. 사실 집합을 효율적으로 합침으로써 복사의 횟수를 $\mathcal{O}(Q \log Q)$회로 줄일 수 있습니다.

부모 정점의 집합과 자식 정점의 집합을 합칠 때 자식 정점의 집합은 더 이상 쓰이지 않으므로 한쪽을 버려도 됩니다. 항상 크기가 작은 집합 원소를 크기가 큰 집합으로 합치고, 크기가 작은 집합을 버리면 남은 집합의 크기 $N$은 크기가 큰 집합의 두 배 이상이 됩니다. 따라서 모든 원소는 크기 $N$인 집합에 합쳐지기까지 $\mathcal{O}(\log N)$회 복사됩니다. 루트 방문 종료 시에 루트의 집합에는 정확히 $Q$개의 원소가 있으므로, 전체 복사 횟수는 $\mathcal{O}(Q \log Q)$회가 됩니다. 이를 작은 집합에서 큰 집합으로 합치는 기술^{Small-To-Large Technique}이라고 합니다.

집합 자료 구조의 기본 연산에 $\tilde{\mathcal{O}}(1)$ 시간이 걸리는 것을 고려하면 전체 실행 시간은 $\tilde{\mathcal{O}}(V + Q)$가 됩니다. 이 방식은 여러 정점의 최소 공통 조상을 구할 때도 쉽게 응용할 수 있다는 장점이 있습니다. 일반적으로 트리 압축^{Tree Compression}을 사용하여 푸는 것으로 알려진 문제를 이 알고리즘으로 풀 수 있는 경우가 있습니다.

분리 집합

여기서 한 가지 관찰을 더 해 보겠습니다. A의 방문 종료 후 자식 정점을 부모 정점과 합치는 연산을 반복했을 때, B의 방문 종료 시점에는 A와 최소 공통 조상이 합쳐져 있을 것입니다. A와 B가 처음으로 조상으로부터 갈라지는 지점이 최소 공통 조상이므로, A의 방문 종료 후 B를 방문하기 위해서는 다시 최소 공통 조상까지 이동해야 하기 때문입니다.

B의 방문 종료 시에 A가 어느 조상과 합쳐져 있는지 알 수 있다면 최소 공통 조상을 알 수 있습니다. 이를 가능케 해 주는 자료구조가 분리 집합 자료구조^{Disjoint Set Data Structure}입니다. 분리 집합 자료구조는 서로소인 집합을 합치고, 집합의 원소를 통해 집합의 대표 원소를 찾을 수 있는 자료구조입니다. 구체적으로 다음 연산을 지원합니다.

• 처음에 $N$개의 집합이 있고, $i$번째 집합은 $i$를 원소로 가집니다.
• 원소 $i$를 포함한 집합과 원소 $j$를 포함한 집합을 합칩니다.
• 원소 $i$를 포함한 집합의 대표 원소를 구합니다.
• 두 연산에는 $\mathcal{O}(\alpha(N))$ 분할 상환 시간이 걸립니다. $\alpha(N)$은 역애커만 함수로, 상수에 가까울 정도로 매우 느리게 증가하는 함수입니다.

이를 이용하여 다음 알고리즘을 고안할 수 있습니다. 먼저, 각 정점 크기만큼의 분리 집합을 구성합니다. 분리 집합의 $i$번째 원소를 $i$번 정점에 대응시킵니다. 정점 방문 종료 시에 부모 정점에 해당하는 원소를 포함한 집합과 자식 정점에 해당하는 원소를 포함한 집합을 합칩니다. 합쳐진 집합의 대표 원소와 부모 정점을 연관시킵니다. 그러면 A를 방문한 후 B를 방문할 때, A에 해당하는 원소가 속한 집합의 대표 원소와 연관된 정점을 찾으면 그 정점이 바로 최소 공통 조상입니다.

이 알고리즘은 $\mathcal{O}(V + Q \alpha(V))$ 시간이 걸리며, Robert E. Tarjan에 의해 처음 고안되었습니다. 분리 집합은 이론적으로도 실증적으로도 매우 빠른 알고리즘이기 때문에 분리 집합을 사용한 최소 공통 조상 알고리즘은 매우 빠르다는 특징이 있습니다.

여기까지 깊이 우선 탐색을 이용해 여러 최소 공통 조상을 한꺼번에 구하는 오프라인 알고리즘들을 알아보았습니다. 다음 글에서는 깊이 우선 탐색과 높이 정보를 모두 사용하는 온라인 알고리즘을 알아보겠습니다.

잘못된 내용이나 추가가 필요한 내용, 궁금하신 내용 등은 덧글로 달아주시면 감사하겠습니다. 읽어주셔서 감사합니다!

다음 글 보기