취미로 코딩하기

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8551번 문제인 Blokada이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/8551

최소한 몇 개의 방향간선을 지워야 1번 정점에서 \(N\)번 정점으로의 연결된 경로가 없게 할 수 있는지를 묻는 문제이다.

이 값은 Max-Flow Min-Cut Theorem에 의해 각 간선의 가중치를 1으로 가정할 때의 1번 정점에서 \(N\)번 정점까지 흘릴 수 있는 최대 유량과 같다.

Dinic's Algorithm을 이용해 최대 유량을 구하고 문제를 해결하자. 모든 간선의 가중치가 1인 유량 그래프에서 Dinic's Algorithm의 시간복잡도는 \(O(\min(E\sqrt{E}, E\sqrt{V^{\frac{2}{3}}}))\)이므로 주어지는 입력의 크기가 상식적이라면 문제를 충분히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
using namespace std;

int ans, src, snk, N, M;
vector<int> G[10002];
bitset<10002> flow[10002];
int lv[10002], trn[10002];
queue<int> que;

bool dfs(int cur) {
    if (cur == snk) return 1;
    int sz = G[cur].size();
    for (int &i = trn[cur]; i < sz; i++) {
        int nxt = G[cur][i];
        if (lv[nxt] != lv[cur] + 1 || !flow[cur][nxt]) continue;
        if (dfs(nxt)) {
            flow[cur][nxt] = 0;
            flow[nxt][cur] = 1;
            return 1;
        }
    }
    return 0;
}

bool bfs() {
    memset(lv, 0, sizeof(lv));
    lv[src] = 1;
    que.push(src);
    while (!que.empty()) {
        int cur = que.front(); que.pop();
        for (auto &nxt:G[cur]) {
            if (lv[nxt] || !flow[cur][nxt]) continue;
            lv[nxt] = lv[cur] + 1;
            que.push(nxt);
        }
    }
    return lv[snk];
}

void dinic() {
    while (bfs()) {
        memset(trn, 0, sizeof(trn));
        while (dfs(src)) ans++;
    }
}

void addedge(int x, int y) {
    flow[x][y] = 1;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
}

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

    cin >> N >> M;
    src = 1, snk = N;
    while (M--) {
        int x, y; cin >> x >> y;
        addedge(x, y);
    }
    dinic();
    cout << ans;
}

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

들어가기 전에

Sum Over Subsets DP, 줄여서 SOS DP는 PS/CP에서는 꽤 유명한 주제라고 생각한다. 이름값이 있는 알고리즘이다보니 글쓴이도 예전에 SOS DP를 익히려고 시도한 적이 있었으나, 그 때에는 개념을 읽어도 이를 적용해 해결할 수 있는 관련 문제를 제대로 찾지 못해 나중으로 미뤘었다.

앞으로 계속 익힐 주제들과 비교했을 때 SOS DP는 더 미루기에는 너무 유명한 주제라는 생각이 들었다. 더 미루지 말고 이런 생각이 든 김에 SOS DP와 그 관련 주제를 공부해 보자.

Submask Enumeration

원소가 \(K\)개인 집합 \(S\)의 각 부분집합 \(A\)는 \(K\)개의 비트를 이용하여 각 원소와 대응되는 비트를 키고 끄는 것으로 모두 나타낼 수 있다. 만약 \(S\)의 모든 각 부분집합 \(m\)에 대하여 각 집합의 모든 부분집합 \(m'\)에 접근하는 알고리즘을 설계한다면 총 몇 개의 \(m'\)에 접근하게 될까?

단순하게 생각하면, 부분집합의 개수가 가장 많은 \(S\)의 부분집합 \(m\)은 \(S\)이고 \(S\)의 부분집합의 개수는 \(2^K\)개이므로 일단 \(O(4^K)\)가 될 것이라고 생각할 수 있다. 그러나 실제로는 이보다 더 적은 \(3^K\)개의 \(m'\)에 접근하게 된다. 

\(A\)의 원소 \(k\)개인 부분집합은 \(\binom{K}{k}\)개이며, 각 부분집합은 \(2^k\)개의 부분집합을 가진다. 따라서 \(A\)의 원소 \(k\)개인 부분집합에서는 총 \(\binom{K}{k}2^k\)개의 \(m'\)에 접근하게 된다.

이를 모든 \(k\)에 대해 합하면 이항정리(binomial theorem)에 의해 \(\sum_{k=0}^K \binom{K}{k}2^k=3^K\)가 된다.

\(3^{17}\)이 129140163이므로, 제한시간이 넉넉하게 주어지는 문제의 경우 이러한 접근법으로 해결할 수도 있다.

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

Sum Over Subsets DP

집합의 부분집합에 대한 몇몇 DP 문제는 위와 같은 접근으로 해결할 수 있지만, 모든 문제를 위와 같이 해결할 수 있는 것은 아니다.

Sum Over Subsets DP는 원소가 \(K\)개인 집합 \(S\)의 모든 부분집합 \(m\)에 대하여 대하여 \(f(m)\)의 값이 알려져 있을 때 \(\sum_{m'\subseteq m} f(m')\)의 값들을 \(O(K2^K)\)에 계산하는 동적 계획법 알고리즘이다.

각 부분집합 \(m\)과 원소의 인덱스 \(k\)에 대하여 \(dp(m, k)\)를 \(m\)의 부분집합 \(m'\)중 \(k\)를 초과하는 인덱스의 원소의 포함 여부는 \(m\)과 상태가 동일한 집합에 대한 \(f(m')\)의 합으로 정의하자. 그리고 초기값으로 \(S\)의 각 부분집합 \(m\)에 대하여 \(dp(m, -1)\)을 \(f(m)\)이라 정의하자.

\(dp(m, k)\)의 합을 구성하는 부분집합들을 인덱스 \(k\)의 원소를 포함하는 부분집합과 그렇지 않은 부분집합으로 나누어 생각해보자. "인덱스 \(k\)의 원소를 포함하는 부분집합"은 \(k\) 이상의 인덱스를 갖는 원소의 포함 여부가 \(m\)와 상태가 동일하다. 따라서 이 집합들의 \(f\)값의 합은 \(dp(m, k-1)\)와 같다. 그리고 "그렇지 않은 부분집합"의 \(f\)값의 합은 \(m\)에서 인덱스 \(k\)의 원소를 제거한 집합 \(m^*\)에 대하여 인덱스가 \(k\) 이상의 인덱스를 갖는 원소의 포함 여부가 \(m^*\)와 동일한 부분집합 \(m'\)들에 대한 \(f(m')\)의 합과 같다.

위의 관계를 식으로 나타내면 다음과 같다.

\(S\)의 부분집합 \(m\)에 대하여, \(m\)이 인덱스 \(k\)의 원소를 포함할 경우 \(dp(m, k) = dp(m^*, k-1) + dp(m,k-1)\)

\(m\)이 인덱스 \(k\)의 원소를 포함하지 않을 경우 \(dp(m, k) = dp(m, k-1)\)

구하고자 하는 값은 \(dp(S,K-1)\)이므로, 이를 계산하려면 위 형태의 점화식을 \(O(K2^K)\)회 계산하면 된다. 위 점화식을 이루는 연산은 단순 덧셈이니 \(O(1)\)에 실행할 수 있다. 따라서 점화식을 이루는 각 집합에 대한 접근이 O(1)에 이뤄질 수 있으면 이 알고리즘의 시간복잡도는 \(O(K2^K)\)가 된다. 이는 비트마스킹을 이용하여 간단히 해낼 수 있다.

정확히 위의 문제를 해결하고자 하는 경우, \(k\)값에 대한 모든 \(dp\)값을 계산한다면 \(k-1\) 이하의 값은 더 이상 필요없어지므로, \(k\)에 대해 순차적으로 계산하면서 각 \(k\)에 대하여 집합들을 적절한 순서로 방문하는 것으로 \(O(2^K)\)의 메모리를 활용해 문제를 해결할 수도 있다.

Sum Over Supersets DP

Sum Over Subsets DP는 원소가 \(K\)개인 집합 \(S\)의 모든 부분집합 \(m\)에 대하여 \(f(m)\)의 값이 알려져 있을 때 \(\sum_{m\subseteq m'\subseteq S} f(m')\)의 값들을 \(O(K2^K)\)에 계산하는 동적 계획법 알고리즘이다.

이 문제는 앞에서 살펴본 Sum Over Subsets DP와 완전히 동일한 방식으로 해결할 수 있다. 단순히 각 부분집합들을 \(S\)에 대한 여집합에 대응시키면 문제가 Sum Over Subsets DP와 동일해짐을 확인하자.

OR Convolution

두 수열 \(a_0, a_1, \cdots, a_{2^K-1}\)과 \(b_0, b_1, \cdots, b_{2^K-1}\)에 대하여 \(c_m=\sum_{i|j=m}a_ib_j\)을 만족하는 수열 \(c_0, c_1, \cdots, c_{2^K-1}\)를 정의하자. 여기에서 \(|\)은 두 정수의 bitwise OR 연산을 의미한다. 이 때 수열 \(c\)를 수열 \(a\)와 \(b\)의 OR Convolution이라고 한다.

편의를 위해, 집합 \(m'\)에 대하여 \(a_{m'}\)을 \(a\)의 "\(m'\)에 대응되는 비트마스크"번째 수로 정의하자.

그리고 두 함수 \(A\)와 \(B\)를 \(A(m)=\sum_{m'\subseteq m} a_{m'}\), \(B(m)=\sum_{m'\subseteq m} b_{m'}\)으로 정의하자.

이 때, \(A(m)\cdot B(m)\)의 값은 \( \sum_{m'\subseteq m} a_{m'} \cdot \sum_{m'\subseteq m} b_{m'} \)이 된다.

그리고 위의 값은 \(C(m)=\sum_{m'\subseteq m} c_{m'}\)의 값과 같다는 것을 어렵지 않게 알 수 있다.

\(a_n\)과 \(b_n\)으로부터 \(A\)와 \(B\)를 얻는 것은 SOS DP로 어렵지 않게 해낼 수 있다. 그렇다면 \(C\)로부터 \(c_n\)을 얻는 것은 가능할까? \(c_n\)으로부터 \(C\)를 얻는 것은 SOS DP를 통해 어렵지 않게 할 수 있으므로, 이를 거꾸로 수행하면 \(C\)로부터 \(c_n\)을 얻을 수 있다!

AND Convolution

두 수열 \(a_0, a_1, \cdots, a_{2^K-1}\)과 \(b_0, b_1, \cdots, b_{2^K-1}\)에 대하여 \(c_m=\sum_{i\&j=m}a_ib_j\)을 만족하는 수열 \(c_0, c_1, \cdots, c_{2^K-1}\)를 정의하자. 여기에서 \(\&\)은 두 정수의 bitwise AND 연산을 의미한다. 이 때 수열 \(c\)를 수열 \(a\)와 \(b\)의 AND Convolution이라고 한다.

AND Convolution 역시 위의 OR Convolution과 동일한 원리로 수행할 수 있다.

Subset Convolution

\(K\)값이 크지 않다면, 몇몇 문제는 \(O(K^22^K)\) 꼴의 시간복잡도 풀이를 갖기도 한다. 그 예시로 Subset Convolution을 소개한다.

두 수열 \(a_0, a_1, \cdots, a_{2^K-1}\)과 \(b_0, b_1, \cdots, b_{2^K-1}\)에 대하여 \(c_m=\sum_{i|j=m, i\&j=0}a_ib_j\)을 만족하는 수열 \(c_0, c_1, \cdots, c_{2^K-1}\)를 정의하자. 여기에서 \(|\)은 두 정수의 bitwise OR 연산을, \(\&\)은 두 정수의 bitwise AND 연산을 의미한다. 이 때 수열 \(c\)를 수열 \(a\)와 \(b\)의 Subset Convolution이라고 한다.

Subset Convolution이 OR Convolution과 다른 점은 \(i\&j=0\) 조건이 하나 추가된 것이 전부임을 확인하자. 이 점을 이용하면 Subset Convolution을 \(O(K^22^K)\)에 계산할 수 있다.

\(A(m, k)\)와 \(B(m,k)\)를 1인 비트의 개수가 \(k\)개인 \(m\)으로 나타나는 항의 값만을 이용한(나머지 항은 0으로 취급) \(a\)와 \(b\)에 대한 SOS DP의 결과라 하자. 그리고 \(C(m, k)=\sum_{k'=0}^{k}A(m,k')\cdot B(m,k-k')\)과 같이 정의하자. 이렇게 \(C\)를 정의하면 \(k\)가 \(m\)의 1인 비트 개수와 정확히 같을 때 \(A\)와 \(B\)에서 겹치는 비트가 없어야지만 OR 값으로 \(m\)이 정확히 나오게 강제할 수 있으므로, 각 \(k\)에 대하여 SOS DP의 undo하는 과정을 거치면 각 \(m\)에 대하여 \(m\)의 1인 비트 개수 \(k\)에 대해 (undo된) 값을 확인하는 것으로 Subset Convolution의 값을 모두 얻을 수 있다.

여담

bitmasking 문제를 만난다면 먼저 최대한 문제를 단순한 형태로 정리해보고, 두 mask 사이의 subset 관계를 활용하기 좋은 형태일 때 이 글의 내용을 풀이법 후보로 생각해보는 것이 좋다. 한편, mask 사이의 포함관계로 문제를 정리할 수 있는 경우더라도, Held-Karp Algorithm(bitmask TSP)이나 각 bitmask를 정점으로 하는 (방향)그래프에서의 BFS 등 더 쉽고 직관적인 방법을 활용할 수 있는지도 생각해보는 것이 좋다. 쉬운 방법으로도 문제를 해결할 수 있다면, 특히 대회에서는 문제를 굳이 어려운 방법으로 해결할 필요는 없다.

글쓴이의 글에서 소개한 접근 방식은 아니지만(그림 없이 다차원 누적합을 묘사하기 귀찮아서 생략했다), SOS DP를 \(K\)차원의 누적 합과 차이배열로 설명하기도 한다. 이 또한 흥미로운 내용이므로 알아두면 좋다.

관련 문제

이 글에서 Submask Enumeration을 설명하기는 했으나, 굳이 SOS DP로 안 풀어도 되는 제한의 문제를 SOS DP로 해결하는 것을 막으려는 목적으로 설명을 한 것이다. 또한 이 글에서 Subset Convolution을 설명하기는 했으나, 어디까지나 \(O(K^22^K)\)의 문제풀이 예시로 보여주기 위해서 설명했을 뿐 그 활용은 이 글의 범위를 넘는다.

아래의 문제들은 SOS DP, AND Convolution, OR Convolution과 관련된 문제들이다. 몇몇 문제는 Generating Function(생성함수)의 개념이 익숙하지 않다면 어려울 수 있다.

[BOJ25563] AND, OR, XOR

자기 자신에 대한 AND Convolution과 OR Convolution으로 AND와 OR의 경우를 해결할 수 있다. XOR의 경우는 간단하므로 생략한다.

[BOJ13759] &

Sum Over Superset DP의 결과가 나타내는 것이 무엇인지를 잘 생각해보자.

[BOJ23949] Shifts

각각의 guard에 대하여, 각 날 하루를 일했을 때의 \(H\)값을 초기값으로 넣고 Sum Over Subsets DP를 돌리면 나오는 결과가 무엇인지 생각해보자.

[BOJ2803] 내가 어렸을 때 가지고 놀던 장난감

각 장난감 상자는 사용하지 않거나 사용하므로, 각각 장난감의 사용 여부로 Sum Over Subsets DP를 한다면 convolution을 이용하여 문제를 해결할 수 있을 것이다. 그러나 각 장난감에 대하여 Sum Over Subsets DP를 사용하는 것은 당연히 무리다. 이를 최적화할 수 있을까?

[BOJ33102] Counting Pairs

조건을 만족하려면 각 비트의 상태가 어때야 하는지를 잘 생각해보자(1)

[BOJ18719] Binomial

조건을 만족하려면 각 비트의 상태가 어때야 하는지를 잘 생각해보자(2)

[BOJ30966] 관심사

원소의 개수가 가장 많은 공통부분집합이 무엇일까?

[BOJ27574] Digits of Unity

SOS DP와 그 역과정의 의미를 잘 생각해보자.

[BOJ25390] Traveling Junkman Problem

문제 풀이의 부분문제로 SOS DP가 사용될 수도 있다.

[BOJ27841] Problem Setting

주어진 전체집합의 부분집합을 이용해 만들 수 있는 chain의 경우의 수를 구해보자.

참고 자료

https://codeforces.com/blog/entry/45223

https://usaco.guide/plat/dp-sos

https://qwerasdfzxcl.tistory.com/35

https://37zigen.com/subset-convolution/

https://www.acmicpc.net/blog/view/127

https://codeforces.com/blog/entry/92153

https://codeforces.com/blog/entry/115438

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 34316번 문제인 사각형 개수 세기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/34316

\(NM\le10^5\) 제약조건을 눈여겨보자. 이 조건으로부터 \(\min(N,M)\le\sqrt{10^5}\)임을 알 수 있다. 이러한 형태로 문제에서 주어지는 입력에 추가적인 제한을 주는 경우는 제법 자주 나타나므로 잘 알아두는 것이 좋다.

\(N\)과 \(M\) 중 더 작은 값을 행의 개수로 하고, 두 개의 행을 골라 각 열의 두 행의 수의 합을 각각 구하는 작업의 시간복잡도는 \(O(\min(N,M)^2\max(N,M))=O(\min(N,M)NM)\)과 같다. \(NM\le10^5\)와 \(\min(N,M)\le\sqrt{10^5}\)가 성립하므로, 이와 같은 접근의 연산량은 1초 안에 충분히 수행 가능하는 점을 관찰할 수 있다. 여기까지 관찰했다면 이후의 계산은 어렵지 않을 것이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

int R, C;
vector<int> v[316];
ll ans;
int cnt[20];

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

    cin >> R >> C;
    if (R < C) {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) cin >> v[r].emplace_back();
        }
    }
    else {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                cin >> v[c].emplace_back();
            }
        }
        swap(R, C);
    }

    for (int r1 = 0; r1 < R; r1++) {
        for (int r2 = r1 + 1; r2 < R; r2++) {
            memset(cnt, 0, sizeof(cnt));
            for (int c = 0; c < C; c++) {
                cnt[v[r1][c] + v[r2][c]]++;
            }
            for (int i = 2; i < 10; i++) ans += cnt[i] * cnt[20 - i];
            int v1 = cnt[10], v2 = v1 - 1;
            if (v1 & 1) v2 /= 2;
            else v1 /= 2;
            ans += v1 * v2;
        }
    }
    cout << ans;
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 33922번 문제인 책 쌓기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/33922

먼저, 주어진 책들을 가로가 세로 길이 이상인 방향으로 일괄적으로 돌려 생각해도 충분하다는 점을 관찰하자. 가로가 세로 길이 이상인 책 위에 세로가 가로 길이 이상인 책을 얹을 수 있다면 문제 제약에 의해 위의 책을 회전시킨 책도 올릴 수 있으며, 이것이 그 위로 새로 올릴 수 있는 책의 집합을 바꾸지 않기 때문이다.

주어진 책들의 몇몇 쌍에 대하여, 어떤 책을 다른 책 위에 올릴 수 있다는 관계가 성립하며, 이 관계는 poset을 이룬다. 따라서 이 문제는 이 책들의 집합의 poset에서의 최대 antichain의 크기를 구하는 것으로 해결할 수 있다. 같은 antichain에 속한 두 원소는 항상 서로 비교가 불가능해야 하므로, 책을 적절하게 뽑아 적절히 나열했을 때 가로의 길이가 strict하게 증가할 때 세로의 길이 또한 strict하게 증가하게끔 뽑을 수 있은 최대 책의 개수를 구하면 문제가 해결된다.

위의 문제는 LIS를 구하는 것으로 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int N, ans;
int A[200001];
pair<int, int> P[200001];

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

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> P[i].first >> P[i].second;
        if (P[i].first < P[i].second) swap(P[i].first, P[i].second);
    }
    sort(P + 1, P + N + 1, greater<>());
    memset(A, 0x3f, sizeof(A));
    A[0] = 0;
    for (int i = 1; i <= N; i++) {
        int L = 0, R = i;
        while (L < R) {
            int mid = (L + R) / 2 + 1;
            if (A[mid] >= P[i].second) R = mid - 1;
            else L = mid;
        }
        A[L + 1] = min(A[L + 1], P[i].second);
    }
    ans = N;
    while (A[ans] == 0x3f3f3f3f) ans--;
    cout << ans;
}

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 33921번 문제인 아름다운 수열이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/33921

전형적인 0-1 Fractional Programming 문제이다. 0-1 Fractional Programming에 대한 설명은 다음 공부 일지에 서술하였다.

https://measurezero.tistory.com/2371

글쓴이는 구현 연습 겸 이 문제를 Dinkelbach's Algorithm으로 해결했다. 계산 과정에서 64비트 정수 자료형의 오버플로우가 발생할 수 있으므로, 구현 과정에서 128비트 정수 자료형을 사용했다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;

ll N, K, X, Y = 1, XX, YY;
ll A[100001], B[100001];

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

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> B[i]; A[i] = B[i] * B[i];
        A[i] += A[i - 1], B[i] += B[i - 1];
    }
    XX = A[N], YY = B[N];

    while ((lll)X * YY != (lll)Y * XX) {
        X = XX, Y = YY;
        lll val = 0, mx = 0; int qL = 0, qR = 0;
        for (int i = 0, lft = 0; i <= N - K; i++) {
            val += (lll)(A[i] - A[i - 1]) * Y - (lll)(B[i] - B[i - 1]) * X;
            if (val < 0) val = 0, lft = i + 1;
            lll v = val + (lll)(A[i + K] - A[i]) * Y - (lll)(B[i + K] - B[i]) * X;
            if (v > mx) mx = v, qL = lft, qR = i + K;
        }
        if (mx) XX = A[qR] - A[qL - 1], YY = B[qR] - B[qL - 1];
    }

    cout << X / Y << '.'; X %= Y;
    for (int k = 0; k < 10; k++) {
        X *= 10;
        cout << X / Y;
        X %= Y;
    }
}

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

들어가기 전에

글쓴이가 지금까지 참가한 두 오프라인 대회(Good Bye BOJ 2025, Semi Game Cup 4)에 공통적으로 출제된 주제가 있다. 바로 Maximum Flow Minimum Cut Theorem(최대 유량 최소 컷 정리)이다. 이 정리를 활용하는 문제들은 유량 그래프만 제대로 구성하면 그냥 Dinic's Algorithm 등 최대 유량을 구하는 알고리즘을 돌리는 것으로 해결할 수 있다. 따라서 이 유형의 난이도는 유량 그래프의 구성 난이도와 직결된다.

어려운 mincut 문제일수록 주어진 문제 상황을 적절한 유량 그래프로 모델링하는 것은 점점 어려워진다. 심지어 몇몇 문제는 겉으로만 보면 이게 그래프를 써야 하는 문제라는 것을 알기조차 어렵게 서술되어 있기도 하다. 또한, 뭔가 유량으로 풀릴 것 같다는 점을 문제의 다른 부분(입력제한이 작다는 사실 등)으로부터 짐작하더라도, 대회중에 밑바닥부터 유량 그래프를 설계하기에는 시간이 많이 들기도 한다. 그러나 시간이 지나면서 많은 mincut 기출문제가 생겼고, 그중 일부는 같은 원리나 모델링으로 묶을 수 있게 되었다.

이번 글에서는 이름이 붙은 몇몇 mincut 관련 문제들을 정리한다. 이 글에서 소개하는 이름있는 문제들의 해결법의 아이디어를 이해한다면 이들을 적절하게 활용하여 (모든 문제는 아니지만) 다양한 mincut 문제들을 해결할 수 있을 것이다.

이 글은 mincut이 무엇인지부터 다루지는 않는다. 만약 mincut을 모른다면 따로 공부하고 오자.

Maximum Closure Problem

정점의 집합이 \(V\)인 방향그래프 \(G\)의 정점의 부분집합 \(C\)가 Closure이라는 것은 \(G\)의 간선을 따라 \(C\)의 정점으로부터 도달할 수 있는 모든 정점의 집합이 \(C\)가 된다는 것을 의미한다. Maximum Closure Problem은 각 정점에 가중치가 있는 방향그래프 \(G\)의 closure 중 정점의 가중치의 합의 최댓값 또는 그 값을 갖게 하는 closure을 찾는 문제이다. 이 때, 정점의 가중치는 양수와 음수 모두 주어질 수 있다. (음이 아닌 정수만 주어지면 그냥 \(G\)를 고르면 되니 의미없는 문제가 된다.)

이 문제는 다음과 같이 유량 그래프를 구성하는 것으로 mincut으로 해결할 수 있다.

(1) source 정점 \(S\)와 sink 정점 \(T\)를 준비한다.

(2) \(V\)의 정점 중 가중치가 양수 \(w\)인 정점은 \(S\)에서 해당 정점으로 이어지는 최대 용량 \(w\)의 간선을, 음수 \(-w\)인 정점은 해당 정점에서 \(T\)로 이어지는 최대 용량 \(w\)의 간선을 추가한다.

(3) \(G\)에 원래 있던 간선의 최대 용량을 (가상의) 무한대로 설정한다.

(4) (\(V\)의 정점 중 가중치가 양수인 정점의 가중치의 합)에서 위에서 구성한 유량 그래프의 mincut의 크기를 뺀 것이 Maximum Closure의 가중치가 되며, 그 때의 Closure 중 하나는 유량 그래프에서의 mincut을 하나 구했을 때의 \(S\)와 연결된 정점들의 집합이 된다.

각 closure과 위의 유량 그래프에서의 각 cut은 대응되며, 각 cut의 가중치의 합은 closure에서는 (가중치가 양수인 정점 중 closure에 포함되지 않은 정점의 가중치의 합)에서 (가중치가 음수인 정점 중 closure에 포함된 정점의 가중치의 합)을 뺀 것과 같다. 한편, 실제 closure의 가중치의 합은 (가중치가 양수인 정점의 가중치의 합)에서 위의 값을 뺀 것과 같다. (가중치가 양수인 정점의 가중치의 합)은 고정된 값임을 관찰하는 것으로 mincut을 찾으면 maximum closure 또한 구할 수 있게 된다.

Project Selection Problem

Project Selection Problem은 다음과 같은 문제를 말한다.

\(N\)개의 프로젝트와 \(M\)개의 기계가 있다. 각 프로젝트를 마치면 수익이 발생하고, 각 기계를 구입하면 비용이 발생한다. 그리고 각 프로젝트마다 진행에 필요한 기계의 집합이 있으며 그 기계를 구입하지 않으면 해당 프로젝트를 진행할 수 없다. 각 프로젝트는 최대 한 번 진행할 수 있으며, 기계는 한 번 구입하면 그 기계가 필요한 모든 프로젝트에 활용할 수 있다.

처음에 어떠한 기계도 가지고 있지 않을 때, 최대 수익을 얻기 위해 진행해야 하는 프로젝트와 구입해야 하는 기계를 구하여라.

이 문제는 각 프로젝트와 기계 사이의 관계를 간선으로 하는 그래프의 Maximum Closure Problem으로 모델링할 수 있다. 즉, A번 프로젝트를 진행하려면 B번 기계가 필요한 관계를 A에서 B로 향하는 방향간선으로 표현하면, 주어진 문제는 Maximum Closure Problem으로 해결할 수 있음을 알 수 있다.

Maximum Weighted Independent Set of Bipartite Graph

Maximum Weighted Independent Set of Bipartite Graph는 다음과 같은 문제를 말한다.

이분그래프(Bipartite graph) \(G\)가 주어진다. 각 \(G\)의 정점에 양의 가중치가 주어질 때, 가중치의 합이 최대가 되게 하는 independent set과 그 때의 가중치를 구하여라.

bipartite graph에서의 Maximum Weighted Independent Set은 Minimum Weighted Vertex Cover의 여집합과 같다. (Bipartite Matching에서의 둘의 관계를 생각하면 당연하다.) 따라서 Maximum Weighted Independent Set은 Minimum Weighted Vertex Cover을 구하는 것으로 구할 수 있다.

Minimum Weighted Vertex Cover은 다음과 같이 유량 그래프를 구성하는 것으로 mincut으로 해결할 수 있다. 단, \(G\)의 정점의 집합이 \(L\)과 \(R\)의 두 집합으로 분할된다고 가정하자.

(1) source 정점 \(S\)와 sink 정점 \(T\)를 준비한다.
(2) \(L\)의 정점은 \(S\)에서 해당 정점으로 이어지는 해당 정점의 가중치만큼의 용량을 가진 간선을, \(R\)의 정점은 해당 정점에서 \(T\)로 이어지는 해당 정점의 가중치만큼의 용량을 가진 간선을 추가한다.
(3) \(G\)에 원래 있던 간선의 최대 용량을 (가상의) 무한대로 설정한다.
(4) 위에서 구성한 유량 그래프의 mincut의 크기가 Minimum Weighted Vertex Cover의 크기가 되며, 해당 cover에 포함되지 않는 정점의 집합이 Maximum Weighted Independet Set이 된다.

각 vertex cover와 위의 유량 그래프에서의 cut은 대응되며, 따라서 이 그래프에서 mincut을 구하면 자연스럽게 Minimum Weighted Vertex Cover을 구하게 됨을 관찰하자.

여담으로, Maximum Weighted Independent Set 문제는 general graph에서는 NP-Hard이다.

燃やす埋める 문제

燃やす埋める 문제(모야스우메루)는 다음과 같은 문제를 말한다.

처리해야하는 \(N\)개의 쓰레기가 있다. 주어진 쓰레기를 처리하는 방법에는 소각하는 것과 매립하는 것의 두 가지가 있고, \(i\)번째 쓰레기 \(a_i\)를 소각해 처리하면 \(x_i\)의 비용이, 매립해 처리하면 \(y_i\)의 비용이 발생한다. 또한 \(M\)개의 쓰레기의 순서쌍 \(C_i = (a_j,a_k)\)에 대하여, \(a_j\)를 소각하여 처리하고 \(a_k\)를 매립하여 처리하면 추가로 \(c_i\)의 비용이 발생한다. 모든 쓰레기를 처리하는 데에 필요한 최소 비용을 구하여라.

燃やす埋める 문제는 다음과 같이 유량 그래프를 구성하는 것으로 mincut으로 해결할 수 있다.

(1) source 정점 \(S\)와 sink 정점 \(T\)를 준비한다.

(2) 각 쓰레기 \(a_i\) 정점에 대하여, \(S\)에서 \(a_i\)로 이어지는 용량 \(y_i\)의 간선과 \(a_i\)에서 \(T\)로 이어지는 용량 \(x_i\)의 간선을 추가한다.

(3) 각 순서쌍 \(C_i=(a_j,a_k)\)에 대하여, \(a_j\)에서 \(a_k\)로 이어지는 용량 \(c_i\)의 간선을 추가한다.
(4) 위에서 구성한 유량 그래프의 mincut의 크기가 燃やす埋める 문제의 답이 된다.

(2)에서 \(y_i\)와 \(x_i\)의 순서는 바뀐 것이 아님에 유의하자.

각 쓰레기의 처리 방식을 정하면 그에 대응되는 위의 유량 그래프의 cut이 항상 존재한다. 정확히는, 각 쓰레기의 처리 방식을 정하면 그 선택에 따라 발생하는 추가 비용 \(c_i\)들이 발생하며, 이에 대응되는 간선들을 모두 고르는 것이 유량 그래프의 cut이 된다. 한편, 위 그래프의 mincut을 구성하는 간선에는 (\(C_i\)에 대응되는 간선을 제외하고 봤을 때) 각 쓰레기별로 소각과 매립에 대응되는 간선이 정확히 하나씩 들어가는데, 그 이유는 다음의 두 가지 관찰로부터 알 수 있다.

어떤 쓰레기에 대하여 소각과 매립에 대응되는 간선을 하나도 넣지 않으면 그 둘에 대응되는 간선으로 여전히 추가적인 유량을 흘릴 수 있으므로 둘 중 적어도 하나는 cut에 포함되어야 한다.

mincut이 둘을 모두 고른다고 가정하면 이 쓰레기는 mincut에 의해 분리된 \(S\)쪽 그래프와 \(T\)쪽 그래프 중 하나에 속하게 되며, 그 중 같은 쪽에 속한 간선을 지워도 여전히 cut이 되므로 모순이 발생한다.

따라서 위의 유량 그래프의 mincut은 각 쓰레기의 처리 방식을 고르는 방법 중 하나에 항상 대응된다.

여담

燃やす埋める라는 표현은 일본에서 자주 쓰이는 용어이며, 딱히 대체할만한 이름을 찾을 수 없어 그대로 글에 옮겨 적었다.

문제에 따라서 따라 풀이에 쓰이는 유량 그래프 모델링이 유일하지 않은 경우도 많다. 위의 여러 이름있는 유형의 문제를 참고하여 주어지는 문제에 따라 자유롭게 유량 그래프를 구성할 수 있게 되어보자.

mincut 문제유형에 익숙한 읽는이에게 이 글은 비슷한 내용을 계속 반복설명하는 듯한 인상을 줄 수도 있을 것이다. 실제로 위의 내용 중 몇몇은 일부만 알아도 이를 활용하여 다른 몇몇을 해결할 수 있기도 하다. 그럼에도 위의 모든 문제들을 서로 다른 문제인 것 처럼 따로 서술한 이유는 (물론 글쓴이가 공부한 내용을 정리하기 위함도 있지만) 읽는이에게 상대적으로 더 잘 이해되고 더 잘 다가오는 mincut 문제 풀이법과 모델링을 찾기 좋게 하기 위해서이다.

관련 문제

유량 문제 특성상 그래프를 구성하는 방법이 다양하다. 문제에 대한 간단한 설명 외에도 다양한 방식의 풀이가 존재할 수 있다.

[BOJ15273] Open-Pit Mining, [BOJ18771] 오픈소스 버그 잡기

Closure Problem 기본 문제이다.

[BOJ19579] 물건 가져가기

위의 문제와 같지만 결과로 얻는 closure까지 직접 구해야 한다.

[BOJ8402] Travel Agency

글쓴이는 燃やす埋める로 접근하여 해결했다.

[BOJ12936] 영웅은 죽지 않아요

"두 영웅이 같이 부활하면 에너지를 되돌려주는 관계"를 의미하는 가상의 정점을 추가하고, 이 정점과 \(S\) 및 그 대응되는 각 영웅 사이의 관계를 간선으로 잘 표현해보자.

[BOJ35036] 코드배틀

"특정 한 팀이 계속 이기는 상황을 밑바탕으로 깔고, 여기에서 다른 한 팀이 이기는 턴을 어떻게 고를지를 최적화하는 문제"로 생각해보자. 그리고 각 턴이 끝날 때마다의 점수 상황만을 보고 얻는 흥미도를 제외한 다른 흥미도를 얻을 수 있는 방법에 대하여, 각 방법을 의미하는 가상의 노드를 새로 추가하고 이 노드와 \(S\), \(T\), 그 방법에 대응되는 턴 사이의 관계를 간선으로 잘 표현해보자.

[BOJ31150] Flood Fill

0과 1로 채워진 격자 그래프에서의 connected component들끼리의 연결관계는 bipartite graph를 이룬다는 점을 잘 활용해보자. 또한, 모든 칸에 대하여 각 칸의 수가 두 번 이상 뒤집히지 않고도 모든 가능한 최종 색 배열을 완성시킬 수 있다는 관찰을 활용하자.

[BOJ35189] X 칠하기 게임

격자의 각 칸을 체스판의 색 배열과 같이 둘로 나누어 이분 그래프로 생각하는 것은 자주 등장하는 아이디어이다. 특히, 추가 점수를 주는 각 X 모양을 구성하는 칸들이 이 이분그래프의 한 쪽에 모여있다는 점을 잘 활용해보자.

[BOJ30935] Task Assignment to Two Employees

일감을 어떻게 분배해도 어떤 두 일감이 어떤 사람에게 주어졌을 때 그 사람의 최적의 두 일감의 처리 순서는 변하지 않음을 관찰하자. 이를 이용하면 주어진 문제 상황은 각 일감의 쌍에 대하여 두 일감이 같은 사람에게 주어졌는지와 그게 누구인지에 따른 수익 증가의 요소가 있을 때 각 일감을 누구에게 주는 것이 수익을 최대화하는지를 구하는 문제로 바꿀 수 있다.

[BOJ3611] 팀의 난이도

\(G\)의 부분그래프에 대하여 \(\frac{\lvert E\rvert}{\lvert V\rvert}\) 의 최댓값을 구하는 것은 \(\lvert E\rvert - \lambda\lvert V\rvert\)의 최댓값이 0이 되게 하는 \(\lambda\)의 값을 찾는 것과 같다. (참고: 공부기록05)
고정된 \(\lambda\)에 대하여 위 식을 최대화하는 그래프를 찾는 것은 각 간선을 고르면 점수를 1씩 얻고 정점을 고르면 점수를 \(\lambda\)씩 잃으며 각 간선을 골랐을 때 그 간선을 구성하는 양 끝의 두 정점은 항상 골라야하는 관계가 있을 때 정점과 간선을 적절히 골라 얻을 수 있는 점수를 최대화하는 그래프를 찾는 것과 같다. 이 문제는 주어진 그래프의 간선과 정점을 각각 새로운 정점으로 하고 간선과 정점의 관계를 새로운 간선으로 하는 Project Selection Problem으로 모델링할 수 있다.
주어지는 그래프에 간선이 없을 수도 있다는 점에 유의하자.

참고 자료

https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

https://en.wikipedia.org/wiki/Closure_problem

https://codeforces.com/blog/entry/101354

https://kanpurin.hatenablog.com/entry/moyasu-umeru