※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.
들어가기 전에
글쓴이가 지금까지 참가한 두 오프라인 대회(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 기본 문제이다.
위의 문제와 같지만 결과로 얻는 closure까지 직접 구해야 한다.
글쓴이는 燃やす埋める로 접근하여 해결했다.
"두 영웅이 같이 부활하면 에너지를 되돌려주는 관계"를 의미하는 가상의 정점을 추가하고, 이 정점과 \(S\) 및 그 대응되는 각 영웅 사이의 관계를 간선으로 잘 표현해보자.
"특정 한 팀이 계속 이기는 상황을 밑바탕으로 깔고, 여기에서 다른 한 팀이 이기는 턴을 어떻게 고를지를 최적화하는 문제"로 생각해보자. 그리고 각 턴이 끝날 때마다의 점수 상황만을 보고 얻는 흥미도를 제외한 다른 흥미도를 얻을 수 있는 방법에 대하여, 각 방법을 의미하는 가상의 노드를 새로 추가하고 이 노드와 \(S\), \(T\), 그 방법에 대응되는 턴 사이의 관계를 간선으로 잘 표현해보자.
0과 1로 채워진 격자 그래프에서의 connected component들끼리의 연결관계는 bipartite graph를 이룬다는 점을 잘 활용해보자. 또한, 모든 칸에 대하여 각 칸의 수가 두 번 이상 뒤집히지 않고도 모든 가능한 최종 색 배열을 완성시킬 수 있다는 관찰을 활용하자.
격자의 각 칸을 체스판의 색 배열과 같이 둘로 나누어 이분 그래프로 생각하는 것은 자주 등장하는 아이디어이다. 특히, 추가 점수를 주는 각 X 모양을 구성하는 칸들이 이 이분그래프의 한 쪽에 모여있다는 점을 잘 활용해보자.
[BOJ30935] Task Assignment to Two Employees
일감을 어떻게 분배해도 어떤 두 일감이 어떤 사람에게 주어졌을 때 그 사람의 최적의 두 일감의 처리 순서는 변하지 않음을 관찰하자. 이를 이용하면 주어진 문제 상황은 각 일감의 쌍에 대하여 두 일감이 같은 사람에게 주어졌는지와 그게 누구인지에 따른 수익 증가의 요소가 있을 때 각 일감을 누구에게 주는 것이 수익을 최대화하는지를 구하는 문제로 바꿀 수 있다.
\(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
'CP자료모음' 카테고리의 다른 글
| [PS/CP 공부기록] 05. 0-1 Fractional Programming, Dinkelbach's Algorithm (1) | 2026.02.03 |
|---|---|
| [PS/CP 공부기록] 04. Green Hackenbush (0) | 2026.01.28 |
| [PS/CP 공부기록] 03. Cartesian Tree, Treap, Implicit Treap (0) | 2026.01.13 |
| [PS/CP 공부기록] 02. System of Difference Constraints (0) | 2026.01.07 |
| [PS/CP 공부기록] 01. Minimum Steiner Tree in Graph (0) | 2026.01.02 |