'Bitmasking' 태그의 글 목록

Bitmasking

[PS/CP 공부기록] 01. Minimum Steiner Tree in Graph 10:00:42

[PS/CP 공부기록] 01. Minimum Steiner Tree in Graph

2026. 1. 2. 10:00

공부기록을 남기기 시작하며

처음으로 오프라인 대회(Good Bye, BOJ 2025!)를 나가고 느낀 점이 있다.

그동안 쉬운 문제를 빠르게 해결하는 실력을 갖추기 위해 쉬운 문제를 대량으로 풀어왔다. 그 결실이 있었는지, 글쓴이는 대회에서 상대적으로 쉬운 문제를 빠르게 해결할 수 있게 된 것을 느꼈다. 그러나 구현이 많이 필요하거나 고급 이론을 활용해야 하는 문제에서 글쓴이가 많이 약하다고 느꼈다.

하지만 쉬운 문제도 빠르게 못 풀던 예전과는 다르게, 이제는 단순히 쉬운 문제를 반복해서 푸는 것보다 다양한 이론, 알고리즘, 자료구조를 접하고, 구현 실력이 필요한 문제 또한 시도해 대회 환경에서 더 많은 문제를 푸는 것을 목표로 해도 될 것 같는 생각이 들었다.

이제 한동안 잘 모르거나 얕게만 알던 다양한 주제를 공부하고 그 내용을 기록으로 남기려고 한다.

※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.

이번 글에서 살펴볼 주제는 Minimum Steiner Tree in Graph이다.

PS/CP에서 찾아볼 수 있는 Minimum Steiner Tree 문제는 크게 둘로 구분지어 생각할 수 있는 것 같다. 그 중 하나는 그래프에서 정의되어 있고, 다른 하나는 좌표평면 위의 점과 유클리드 거리에 대하여 정의되어 있다. 이 글에서는 전자의 문제를 다룬다.

Minimum Steiner Tree in Graph

먼저 Minimum Steiner Tree가 무엇인지 알아보자.

정점의 집합 \(V\)와 (음이 아닌) 가중치가 있는 간선의 집합 \(E\)로 구성된 연결그래프 \(G\)에 대하여, \(V\)의 (공집합이 아닌) 부분집합을 \(K\)라 하자. 이 때, Steiner Tree는 \(K\)의 모든 정점을 포함하는 \(G\)의 subtree를 말한다. 또한 Minimum Steiner Tree는 모든 Steiner Tree 중 간선의 가중치의 합이 가장 작은 Steiner Tree를 말한다. 또한 \(K\)에 속한 정점들을 Terminal이라고 부른다.

\(K\)의 크기가 1이면 Minimum Steiner Tree는 그 정점만을 포함한 가중치 0의 subtree가 됨은 자명하다. 또한 \(K\)의 크기가 2이면 두 정점을 잇는 최단경로의 형태가 Minimum Steiner Tree가 될 것이며, \(K\)의 크기가 3이면 각 정점에 대하여 세 정점으로부터의 최단거리의 합을 구했을 때 그 합이 가장 작은 정점을 중심으로 \(K\)의 세 정점을 최단거리로 이은 형태가 Minimum Steiner Tree가 될 것이다. 그러나 \(K\)의 크기가 4 이상이면 이와 같은 단순한 접근은 점점 어려워지게 된다.

이 문제는 Minimum Spanning Tree를 구하는 문제의 일반화로 생각할 수 있다. \(K=V\)인 경우 Minimum Spanning Tree와 정확히 같은 문제가 됨을 관찰하자. 그러나 이 문제는 NP-Hard 문제임이 잘 알려져있다. 따라서 P=NP가 아닌 이상에는 Minimum Steiner Tree 문제를 다항시간 내에 해결하기 어려울 것이다.

Minimum Steiner Tree를 구하기 위한 다양한 approximation algorithm이 존재하지만 이러한 알고리즘은 PS/CP에서 나오는 문제들과 잘 맞지 않는다. 일반적으로 PS/CP에서는 정확한 해를 구할 것을 요구하는 문제가 주로 나오기 때문이다. 따라서 이 글에서는 Exact Minimum Steiner Tree를 구하는 내용만을 다룬다.

Dreyfus-Wagner Algorithm

Minimum Steiner Tree를 구하는 알고리즘으로 Dreyfus-Wagner 알고리즘이 잘 알려져 있다. 이 알고리즘은 다음과 같은 DP로 진행된다.

\(K\)의 부분집합 \(K'\)과 \(V\)에 속하는 정점 \(v\)에 대하여 \(dp[K'][v]\)를 \(K'\)에 속한 모든 정점을 포함하면서 \(v\) 또한 포함하는 가장 가중치가 작은 \(G\)의 서브트리의 가중치로 정의하자. 즉, \(dp[K'][v]\)는 \(K'\cup\{v\}\)에 대한 Minimum Steiner Tree의 가중치를 나타낸다.

이 때, \(dp[K'][v]\)의 값은 다음과 같은 두 가지 방식으로 다른 상태로부터 계산할 수 있다.

(1) 이 상태를 나타내는 Minimum Steiner Tree에서 \(v\)의 degree가 2 이상인 경우:

\(K'\)을 두 집합 \(K_1\)과 \(K_2\)로 나누면 \(dp[K'][v]=dp[K_1][v]+dp[K_2][v]\)가 되게끔 할 수 있다.

(2) 이 상태를 나타내는 Minimum Steiner Tree에서 \(v\)의 degree가 1인 경우:

그 Minimum Steiner Tree에서 \(v\)와 연결된 정점을 \(u\)라 하고, 그 연결 간선의 가중치를 \(w\)라 하자. 이 때 \(dp[K'][v]=dp[K'][u]+w\)가 성립한다.

(1)의 경우, \(K'\)의 모든 부분집합에 대하여 문제를 먼저 해결해둔다면 계산을 쉽게 처리할 수 있다. 다만 이 값을 계산하는 시점에는 \(K'\)를 어떻게 쪼개야 최적인지에 대한 정보를 가지고 있지 않으므로, 가능한 모든 방법으로 \(K'\)를 쪼개봐야 한다는 점에 유의하자.

(2)의 경우, 이 과정을 degree가 1이 아닌 정점이 나올 때까지 반복하면 \(K'\)의 Minimum Steiner Tree를 얻게 됨을 관찰하자. 따라서, \(K'\)의 Minimum Steiner Tree의 값에서부터 relaxation을 반복하여 값을 갱신해나가는 것으로 (2)의 계산을 처리할 수 있다. 이해하기 어렵다면 Dijkstra 알고리즘의 relaxation 과정을 생각해보자.

기저 상태를 각 \(K\)의 원소 \(k\)에 대하여 \(dp[\{k\}][k]\)의 값을 0, 나머지 상태의 값을 전부 (가상의) 무한대로 설정하고 위와 같이 \(dp\)의 값을 계산해 문제를 해결하자.

relaxation 과정에 binary heap을 사용한다고 가정하면, Dreyfus-Wagner 알고리즘의 시간복잡도는 \(O(V3^K+(V+E)2^K\log V)\)와 같다. 여기서 \(V3^K\)는 DP에서의 (1)의 처리에 드는 시간복잡도이고, \((V+E)2^K\log V\)는 DP에서의 (2)의 처리에 드는 시간복잡도이다. (1)의 시간복잡도를 이해하기 어렵다면, bitmasking으로 \(K\)까지의 정수가 나타내는 각 집합에 대하여 각각의 부분집합의 개수의 합이 \(O(3^K)\)과 같다는 내용을 찾아보도록 하자.

따라서 Dreyfus-Wagner 알고리즘은 \(V\)와 \(E\)가 어느 정도 크더라도 \(K\)가 충분히 작다면 PS/CP에서 충분히 제한 내에 사용할 수 있다.

Dreyfus-Wagner 알고리즘 구현 팁

bitmask를 활용하여 표현된 어떤 집합을 나타내는 정수\(x\)가 있을 때, \(x\)의 모든 부분집합은 초기값이 \(x\)인 변수 \(x'\)에 대하여 \(x':=(x'-1)\&x\)를 반복하는 것으로 모두 접근할 수 있다.

Dijkstra 알고리즘을 문제 제한에 따라 다양한 방식으로 최적화할 수 있듯이, 위 알고리즘의 중간 과정인 relaxation은 문제 상황에 따라 문제에 따라 다양하게 변형해 복잡도를 낮출 수 있다. 예를 들어 노드가 적지만 dense한 그래프의 경우 우선순위 큐를 사용하지 않고 \(O(N^2)\)으로 relaxation을 처리할 수 있다. 또한 가중치의 크기가 매우 제한적이라면 Dial 알고리즘처럼 버킷을 활용해 relaxation을 처리할 수 있다.

Rectilinear Minimum Steiner Tree

Rectilinear Minimum Steiner Tree 문제는 좌표평면 위에 \(K\)개의 점이 주어졌을 때 이 점들을 축과 평행한 선분만으로 모두 연결하기 위해 그어야 하는 선분의 길이의 최솟값을 구하는 문제이다.

주어진 \(K\)개의 점에 대하여 두 축과 각각 평행한 직선을 그려 얻게 되는 격자형태의 그래프를 Hanan Grid라고 부른다.

\(K\)개의 점에 대한 Rectilinear Minimum Steiner Tree는 이 \(K\)개의 정점으로 생성된 Hanan Grid 위에서 항상 찾을 수 있다. 따라서 \(K\)가 충분히 작을 경우 Dreyfus-Wagner 알고리즘으로 Rectilinear Minimum Steiner Tree 문제 또한 해결할 수 있다.