Heavy-Light Decomposition

서론

알고리즘 문제를 풀다 보면 많은 경우에 문제를 그래프 문제로 모델화할 수 있음을 보게 됩니다. 여러 요소들간의 관계가 주어지는 경우에는 각 요소를 정점으로, 관계를 간선으로 두는 방식의 모델화가 자주 사용되고, DP 문제는 대다수의 경우 DAG(Directed Acyclic Graph)의 형태로 각 상태가 이어지게 되므로 역시 그래프 문제의 일종으로 볼 수 있습니다.

그런데 특별한 제약 조건이 없는 그래프 문제의 경우 이 모델화에 성공하면 대체로 문제가 쉬워지거나, 전형적인 알고리즘을 요구하는 문제로 바뀌게 됩니다. 오히려 제약 조건이 추가된 형태일수록 그 조건에 의해 나타나는 특성을 코어까지 활용해야 하는 어려운 문제를 자주 마주치게 됩니다.

트리는 바로 그 중심에 서있는 자료구조라고 할 수 있습니다. 일반적인 형태의 그래프라면 효율적으로 계산하는 것이 매우 어렵거나 아예 다항 시간에 계산하는 것조차 불가능한 문제들을 트리에서는 해결할 수 있는 경우가 많기 때문에 트리에 대해서는 정말 무자비한(?) 질의를 던지는 문제들을 종종 볼 수 있습니다. 이번 글에서는 트리이기 때문에 사용할 수 있는 테크닉 중 하나인 heavy-light decomposition 에 대한 기본적인 설명과, 이를 사용하여 어떤 문제들을 풀 수 있는지를 알아보겠습니다.

Heavy-Light Decomposition

일반적인 그래프에서는 “어떤 정점 $u$에서 다른 정점 $v$로 가는 경로”와 같은 것에 대한 문제를 풀기가 매우 어렵고, 제시할 수 있는 문제의 유형이 한정적입니다. 그러한 경로가 무수히 많을 수 있고, 그 중에서 어떠한 특성(예를 들면 최단경로)을 가진 것에 대해서만 알아내려고 해도 만만치 않은 시간 복잡도를 요구하기 때문입니다. 심지어 여기에 그 경로 위의 정점이나 간선의 속성을 변화시키는 연산을 수행하고자 한다면 각 연산을 효율적으로 처리하는 것은 불가능에 가까워집니다.

하지만 트리라면 이야기가 달라집니다. 서로 다른 두 정점을 잇는 단순 경로는 반드시 하나만 존재한다는 특징이 있기 때문입니다. 물론 트리의 경우에도 매번 이 경로를 나이브하게 구하고자 한다면 결국 트리 전체를 순회해야 하기 때문에 정점의 개수가 $N$개인 트리에서 $O(N)$ 시간이 소요되기 때문에 보다 효율적인 방법이 필요해집니다. 이러한 종류의 문제를 해결하기 위해 일반적으로 가장 먼저 배우는 테크닉은 sparse table을 활용한 LCA(Lowest Common Ancestor) 알고리즘인데, 이에 대해서는 이 글에서 다루지는 않겠습니다. Sparse table은 간단한 LCA 문제를 해결하는 데에는 무리가 없고 비교적 직관적인 접근법을 사용한다는 장점이 있지만, 공간 복잡도가 $O(NlogN)$이고 변화에 취약하다는 것이 큰 약점입니다.¹

Heavy-light decomposition, 줄여서 HLD로 불리는 테크닉은 트리에 대한 새로운 관점을 보여줍니다. 트리를 정점 단위가 아닌 chain 단위로 분할하여 마치 1차원 배열의 묶음처럼 다룰 수 있게 해줍니다. 이게 대체 무슨 뜻인지 구체적으로 알아보겠습니다.

수행 방법

HLD에서 chain이란 특정 노드에서 시작하여 연속적으로 어떤 자식 노드로 내려가여 리프까지 도달하여 얻어지는 노드 집합을 의미합니다. 무조건 한 방향으로 진행하기 때문에 그 형태는 반드시 일자형이 됩니다.

기본적인 과정은 루트 노드²에서 출발하는 체인을 만드는 것으로 시작하여, 재귀적으로 한쪽 자식을 선택하여 그 체인을 이어나간 뒤, 선택되지 않은 자식들 각각에 대해 그 자식 노드에서 출발하는 새로운 체인을 만들어주는 것입니다. 중요한 것은 여기서 어느 자식을 자기 체인에 묶어줄 것인지를 선택하는 방법인데, 이 부분이 HLD의 효율성을 보장해주는 매우 중요한 규칙입니다. 자식을 루트로 하는 서브트리의 크기가 가장 큰 것을 자기 체인에 묶어줍니다.

그림으로 표현하면 아래와 같습니다. 각 정점에 쓰인 수는 해당 노드를 루트로 하는 서브트리의 노드의 수를 의미합니다. 이 값은 먼저 전체를 한 번 DFS로 순회하면서 쉽게 계산해둘 수 있습니다.

트리의 초기 상태

루트 노드부터 체인을 만들기 시작합니다. 자식들 중 가장 서브트리의 크기가 큰 노드는 가장 왼쪽 노드이니 왼쪽으로 체인을 이어줍니다.

6 4 5 중에 6이 가장 크다.

왼쪽의 노드의 자식 중에서도 다시 가장 왼쪽의 자식의 서브트리가 가장 크므로 가장 왼쪽으로 이어줍니다.

3 1 1 중에 3이 가장 크다.

여기서는 두 자식의 서브트리의 크기가 서로 같기 때문에 아무 쪽으로나 이어도 됩니다.

1 1 중에서는 아무 1이나 골라도 된다.

그 다음은 다시 부모로 돌아가서 다른 쪽 자식에 대해 새로운 체인을 시작해 줍니다. 이 노드는 또한 리프 노드이기도 하기 때문에, 자신만이 이 체인의 유일한 멤버가 됩니다.

단독으로 체인 생성.

마찬가지로 더 부모 쪽으로 돌아가서도 나머지 자식들에 대해 개별적인 체인이 각각 생성됩니다.

역시 단독으로 체인 생성.

이제 다시 루트까지 되돌아와서, 나머지 자식들에 대해 개별적인 체인을 만들어 탐색해줘야 합니다. 나머지 자식들에 대한 탐색 순서는 상관 없습니다. 가장 서브트리의 크기가 큰 자식에 대해서만 체인을 묶어주는 것으로 충분합니다. 가운데로 먼저 내려가 보고 이전과 같은 방식으로 진행하고 나면 다음과 같이 됩니다.

가운데 자식의 서브트리의 decomposition을 끝낸 모습.

마지막으로 루트의 오른쪽 자식에 대해서도 분할을 모두 끝내면 최종적으로 다음과 같은 모습이 만들어집니다.

HLD 완성.

효율성

이렇게 분할된 트리가 시간 복잡도 면에서 어떤 효율성을 가지는지 분석해 보겠습니다. 어떤 노드 $A$를 루트로 하는 서브트리의 크기를 $n(A)$라고 합시다. $A$에서 연결되는 체인은 항상 서브트리의 크기가 가장 큰 자식 쪽으로 가게 되므로, 체인이 연결되지 않은 임의의 자식 노드 $B$에 대해 $n(B) \le \frac{n(A)}{2}$를 만족하게 됩니다. 이를 루트부터 재귀적으로 거치게 되면 모든 노드에 대해 루트와 그 노드를 잇는 경로에는 최대 $O(logN)$개의 서로 다른 체인만이 존재함을 볼 수 있습니다.

따라서 문제를 두 노드를 잇는 경로에 있는 체인들에 대한 연산으로 바꾸어 풀 수 있다면, 각 연산은 $O(logN)$만에 수행될 수 있습니다. 물론 각 체인에 수행되는 연산이 복잡하다면 무용지물이지만, 체인은 단순한 1차원의 배열이므로 다양한 연산을 더 효율적으로 처리할 수 있는데, 어떤 것들이 가능한지는 조금 뒤에 알아보겠습니다.

마지막으로 공간 복잡도는 $O(N)$으로 sparse table에 비해 더 좋음을 알 수 있습니다.

코드

백준 온라인 저지 11438번 LCA 2를 HLD로 푸는 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100005];
int sz[100005], par[100005];

int dfs(int i, int p)
{
	par[i] = p;
	sz[i] = 1;
	for (int x : adj[i])
		if (x != p)
			sz[i] += dfs(x, i);
	return sz[i];
}

vector<int> chain[100005];
int depth[100005];
int chain_number[100005], chain_index[100005];

void HLD(int i, int p, int cur_chain, int d)
{
	depth[i] = d;
	chain_number[i] = cur_chain;
	chain_index[i] = chain[cur_chain].size();
	chain[cur_chain].push_back(i);

	int heavy = -1;
	for (int x : adj[i])
		if (x != p && (heavy == -1 || sz[x] > sz[heavy]))
			heavy = x;
	if (heavy != -1)
		HLD(heavy, i, cur_chain, d);
	for (int x : adj[i])
		if (x != p && x != heavy)
			HLD(x, i, x, d + 1);
}

int LCA(int a, int b)
{
	while (chain_number[a] != chain_number[b])
	{
		if (depth[a] > depth[b])
			a = par[chain_number[a]];
		else
			b = par[chain_number[b]];
	}
	return chain_index[a] > chain_index[b] ? b : a;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m, i;
	cin >> n;
	for (i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, 0);
	HLD(1, 0, 1, 0);
	cin >> m;
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		cout << LCA(a, b) << '\n';
	}
}

실행 흐름을 따라가 봅시다. 간선 정보가 모두 들어온 후 가장 먼저 하는 일은 각 서브트리의 크기를 구하는 것입니다. 그를 위해 dfs 함수가 트리를 순회합니다.

vector<int> adj[100005];
int sz[100005], par[100005];

int dfs(int i, int p)
{
	par[i] = p;
	sz[i] = 1;
	for (int x : adj[i])
		if (x != p)
			sz[i] += dfs(x, i);
	return sz[i];
}

adj에 담긴 간선 정보를 이용하여 트리를 순회하고 자식들로부터 서브트리들의 크기를 돌려받아 자신의 서브트리 크기를 sz에 저장합니다. 또한 부모가 누구인지 기록하는 것도 이후 유용하기 때문에 (그리고 이 문제에 필요하기 때문에) par 배열에 기록해 둡니다.

한 번 순회를 통해 필요한 정보를 모두 얻었으면 그 다음은 실제 HLD를 수행해야 합니다. 여기에 쓰이는 배열들에는 다음과 같은 것들이 있습니다.

vector<int> chain[100005];
int depth[100005];
int chain_number[100005], chain_index[100005];

chain: 각 체인에 속한 노드들의 번호를 부모 -> 자식 순으로 저장합니다. i가 시작점인 체인은 chain[i]에 저장됩니다.
depth: 각 노드가 속한 체인의 깊이를 나타냅니다. 즉, depth[i]는 i번 노드가 루트 노드가 속한 체인에 도달하기까지 거쳐가야 하는 서로 다른 체인의 수를 나타냅니다.
chain_number: 각 노드가 속한 체인의 번호입니다.
chain_index: 각 노드가 자신이 속한 체인에서 몇 번째 노드인가를 나타냅니다.

HLD를 수행하는 코드는 다음과 같습니다.

void HLD(int i, int p, int cur_chain, int d)
{
	depth[i] = d;
	chain_number[i] = cur_chain;
	chain_index[i] = chain[cur_chain].size();
	chain[cur_chain].push_back(i);

	int heavy = -1;
	for (int x : adj[i])
		if (x != p && (heavy == -1 || sz[x] > sz[heavy]))
			heavy = x;
	if (heavy != -1)
		HLD(heavy, i, cur_chain, d);
	for (int x : adj[i])
		if (x != p && x != heavy)
			HLD(x, i, x, d + 1);
}

HLD 함수에 전달되는 인자 중 i는 현재 노드 번호, p는 부모 노드 번호, cur_chain은 현재 노드가 속한 체인의 번호, d는 현재 체인의 깊이를 나타냅니다.

HLD가 호출되면 먼저 현재 노드의 depth에 현재 체인의 깊이(d)를 저장하고, 현재 노드가 어떤 체인인지(cur_chain)를 chain_number에 저장하며, 그 체인에서 몇 번째 노드가 되는지를 현재까지 chain[cur_chain] 벡터에 저장된 원소의 개수를 통해 알아내어 chain_index에 저장하고 자신을 chain[cur_chain]에 추가합니다.

그 다음은 자식 노드들 중 가장 무거운(서브트리의 크기가 가장 큰) 노드가 무엇인지 알아내기 위해 간선들을 순회하여 찾아내고 이를 heavy에 저장합니다. 만일 자식이 하나라도 있다면 heavy가 -1이 아니게 될 것입니다. HLD를 이 자식에 대해 먼저 호출하여 현재 체인 번호와 깊이를 유지한 채로 분할을 진행하게 하고, 그쪽 자식의 순회가 모두 끝나고 나면 그 자식을 제외한 다른 자식들에 대해 각각 HLD를 새로운 체인 번호(그 자식의 번호)를 부여하여 한 단계 더 깊은 깊이에서 분할을 진행하도록 만듭니다.

이제 마지막으로 이렇게 완성된 HLD 정보를 가지고 LCA를 어떻게 수행하는지 봅시다.

int LCA(int a, int b)
{
	while (chain_number[a] != chain_number[b])
	{
		if (depth[a] > depth[b])
			a = par[chain_number[a]];
		else
			b = par[chain_number[b]];
	}
	return chain_index[a] > chain_index[b] ? b : a;
}

기본적인 아이디어는 sparse table을 사용한 것과 비슷합니다. 서로 같은 위치에 도달할 때까지 깊이가 깊은 쪽부터 먼저 끌어올리는 것을 반복합니다. 단, sparse table에서는 노드 자체가 같아질 때까지 끌어올리지만, HLD에서는 노드가 속한 체인이 같아질 때까지 끌어올린다는 것이 차이점입니다. 위에서 보였던 것과 같이 임의의 노드에서 루트까지 올라가는 횟수는 $O(logN)$번이므로, 두 노드에서 각각 끌어올리는 횟수 역시 $O(logN)$번이 됩니다.

끌어올릴 때는 서로 다른 체인으로 넘어가기 때문에 자신이 속한 체인의 부모 체인이 무엇인지를 알아야 하고, 그 정보는 par 배열에 기록되어 있습니다. par[chain_number[a]]는 a가 속한 체인(그 체인의 시작 노드)의 부모이기 때문에 부모 체인에서 현재 체인으로 넘어오는 길목을 정확하게 찾아낼 수 있습니다.

서로 같은 체인까지 올라왔을 때 그 중 LCA가 누구인지를 판별하는 것은 chain_index를 통해 알 수 있습니다. chain_index 값이 루트로부터 거리가 더 먼 노드이기 때문에, 둘 중 더 작은 값을 가지는 쪽이 LCA에 해당함을 알 수 있습니다.

예시 그림을 통해 LCA의 과정을 표현하면 다음과 같습니다. 위에서 사용한 그림에서 각 체인의 시작점마다 그 체인의 깊이를 위에 표시했습니다.

LCA를 찾고자 하는 두 노드.

오른쪽의 노드가 속한 체인의 깊이가 더 깊기 때문에 오른쪽의 화살표를 부모 체인으로 올립니다.

두 체인의 깊이가 같아졌다.

이제 두 노드의 체인 깊이가 같아졌습니다. 왼쪽 노드가 b라고 가정하고, b를 부모 체인으로 올려봅시다.

다시 오른쪽 노드가 속한 체인이 깊어졌다.

이제 왼쪽 노드가 속한 체인의 깊이가 더 낮으니, 오른쪽 화살표를 위로 올려야 합니다.

서로 같은 체인에 속하게 되었다.

서로 같은 체인에 들어왔으니, 루프를 탈출하고 둘 중 누가 체인 내에서 더 작은 인덱스를 가지는지 비교합니다. 이 경우 오른쪽의 화살표의 인덱스가 더 작으니, 오른쪽 화살표가 가리키는 노드가 LCA가 됨을 알 수 있습니다.

HLD의 활용법

위에서는 HLD의 가장 기본적인 활용인 LCA에 대해서만 깊이있게 살펴보았지만, 이것만으로는 아직 트리를 체인 단위로 분할한 것의 장점이 크게 와닿지 않습니다. 이 문단에서는 이후 HLD를 활용하는 방법 몇 가지에 대해 간략하게 소개합니다.

경로 만들기

LCA를 찾을 수 있으니, 두 정점을 연결하는 경로 전체 역시 얻어낼 수 있습니다. LCA를 구하는 과정에서 각 정점과 그 정점이 속한 체인의 시작점을 분리해내면 전체 경로가 $O(logN)$개의 ‘선분’으로 표현됩니다. 각 체인에 대한 유의미한 정보를 가지고 있다면 분리된 ‘선분’ 각각에 대해서도 정보를 빠르게 얻어내도록 설계가 가능합니다.

세그먼트 트리

체인이 선분 형태라는 것은 너무나 강력한 활용 가치를 만들어 냅니다. 바로 각 체인을 세그먼트 트리 내에서 연속된 원소로 표현할 수 있다는 점입니다. HLD 수행 시 가장 무거운 자식을 먼저 방문하도록 정해놓으면 같은 체인에 속하는 정점들이 항상 연속적으로 탐색되게 만들 수 있습니다. 따라서 오일러 투어 방식으로 방문 순서를 적어놓으면 단 하나의 세그먼트 트리 내에서 여러 체인들이 각자의 구간을 가진 것으로 표현이 가능합니다.³

물론 세그먼트 트리의 특성상 각각의 선분에 대해 연산하는 것이 추가로 $O(logN)$이 되는 것은 피할 수 없지만, 위의 ‘경로 만들기’와 합쳐도 전체 연산에 $O(log^2N)$밖에 소요되지 않기 때문에 많은 문제에서 충분히 사용이 가능한 시간 복잡도가 됩니다.

Disjoint Set과의 관계

Disjoint set(혹은 union find) 알고리즘에서 시간 복잡도를 단축시키는 방법으로 여러 가지가 있는데, 그 중 하나로 알려진 것이 ‘크기가 작은 쪽을 큰 쪽에 붙이는’ 방법입니다. 이 경우 별도의 최적화 기법을 사용하지 않아도 전체를 union 하는 데에 $O(NlogN)$ 시간이 걸린다고 알려져 있습니다. 또한 union을 할 때마다 작은 쪽에 있는 원소들에 대한 정보를 모조리 큰 쪽으로 옮겨도 $O(NlogN)$이 유지됩니다.

이는 각 노드가 속하는 트리가 변하는 횟수가 많아야 $O(logN)$번이라는 것을 보이면 되는데, 자신이 속한 트리의 루트가 다른 트리의 루트의 자식이 되려면 다른 트리의 크기는 최소한 자신이 속한 트리의 크기만큼이어야 하므로, 자신이 현재 속한 트리의 크기는 합쳐진 이후의 트리의 크기의 반 이하입니다. 따라서 find 연산을 수행할 때마다 걸리는 시간 역시 $O(logN)$이며⁴, 전체 과정에서 노드 정보가 다른 트리로 옮겨지는 횟수 역시 각각 $O(logN)$번이니 전체 시간 복잡도가 $O(NlogN)$임을 보일 수 있습니다.

이는 HLD가 보이는 특성과 근본적으로 같은데, 서로 다른 두 트리가 합쳐지는 순간을 역으로 분할하는 것이 곧 HLD라고 할 수 있습니다. 각 노드에 대해 이러한 과정이 $O(logN)$번밖에 일어나지 않기 때문에, 역으로 수행해도 체인을 $O(logN)$개만 거쳐서 도달할 수 있도록 분할이 가능한 것입니다.

결론

트리에 대한 깊은 탐구를 해보지 않았다면 HLD라는 기법은 매우 신선할 것입니다. 일반적인 그래프의 일종으로 다루는 것을 넘어, 트리이기 때문에 가능한 방법을 통해 여러 체인으로 분할한다는 발상은 저에게도 상당한 충격을 주었습니다.

그러나 HLD만으로 트리의 모든 것을 해결할 수는 없는데, 이는 트리의 제한적인 특성을 이용하여 요구할 수 있는 테크닉이 무궁무진하기 때문일 것입니다. 그래프의 가장 기본적이면서도 가장 어려운 트리를 정복하기 위해서는 이 HLD를 시작으로 수많은 기법을 익히고 또 연습해야 할 것입니다.

Table에 구간 내 정점들에 대한 정보를 같이 저장한다면, 정점 하나의 속성에 변화가 생겼을 때 최악의 경우 sparse table의 모든 엔트리를 업데이트해야 할 수도 있습니다. ↩
루트가 정해지지 않은 트리라면 임의로 정해도 됩니다. ↩
이러한 방법을 쓰지 않고 체인별로 별개의 세그먼트 트리를 만들어도 됩니다. 구현이 복잡해지지만, 경우에 따라서는 효율이 높아질 수도 있습니다. ↩
한 트리가 다른 트리 밑으로 들어갈 때마다 기존 트리의 노드들의 깊이가 1씩 깊어지기 때문입니다. ↩

Heavy-Light Decomposition

서론

Heavy-Light Decomposition

수행 방법

효율성

코드

HLD의 활용법

경로 만들기

세그먼트 트리

Disjoint Set과의 관계

결론

2018 ICPC world Finals C. Conquer the world와 Tree DP optimization

C++ STL 컨테이너의 메모리 사용량 (2)