개요
다음과 같은 흐름 네트워크(flow network)가 주어졌다고 가정해 봅시다. s-t 컷(s-t cut)이란 소스(source) 노드 s와 싱크(sink) 노드 t가 서로 다른 집합에 속하도록 그래프를 분할하는 것을 의미합니다. 이때 컷에는 소스 쪽 집합에서 싱크 쪽 집합으로 향하는 간선들이 포함됩니다.
s-t 컷의 용량(capacity)은 컷 집합(cut-set)에 포함된 각 간선 용량의 합으로 정의됩니다. 우리의 목표는 주어진 네트워크에서 최소 용량을 가지는 s-t 컷을 찾고, 해당 최소 컷을 구성하는 모든 간선을 출력하는 것입니다.
예를 들어 입력이 아래와 같다면,
출력은 다음과 같습니다.
[(1,3), (4,3), (4,5)]
알고리즘 접근 방식
이 문제는 포드-풀커슨(Ford-Fulkerson) 알고리즘을 이용해 최대 유량을 먼저 계산한 뒤, 잔여 그래프(residual graph)에서 소스로부터 도달 가능한 노드들을 찾아 최소 컷을 도출하는 방식으로 해결할 수 있습니다. 최대 유량 최소 컷 정리(Max-Flow Min-Cut Theorem)에 따르면, 네트워크의 최대 유량 값은 최소 s-t 컷의 용량과 같습니다.
구체적인 해결 단계는 다음과 같습니다.
- NODES = 6 으로 설정합니다.
- bfs() 함수를 정의합니다. 매개변수는 graph, src, sink, 배열 par 입니다.
- 크기가 NODES인 배열 vis를 선언하고 0으로 초기화합니다.
- 큐(que)를 하나 생성합니다.
- src를 큐에 삽입합니다.
- vis[src] := true, par[src] := -1 로 설정합니다.
- 큐가 빌 때까지 반복합니다.
- u1 := 큐의 첫 번째 원소를 꺼냅니다.
- v1 := 0 부터 v1 < NODES 까지 반복하며,
- vis[v1]이 false이고 graph[u1, v1] > 0 이면
- v1을 큐에 삽입합니다.
- par[v1] := u1 으로 설정합니다.
- vis[v1] := true 로 설정합니다.
- vis[v1]이 false이고 graph[u1, v1] > 0 이면
- vis[sink]가 true이면 true를 반환합니다.
- dfs() 함수를 정의합니다. 매개변수는 graph, src, 배열 vis 입니다.
- vis[src] := true 로 설정합니다.
- i := 0 부터 i < NODES 까지 반복하며,
- graph[src, i]가 0이 아니고 vis[i]가 false이면 dfs(graph, i, vis)를 재귀 호출합니다.
- 메인 로직에서는 다음을 수행합니다.
- 배열 temp_graph를 만들어 graph를 복사합니다.
- 크기가 NODES인 배열 par를 선언합니다.
- bfs(temp_graph, src, sink, par)가 true인 동안 반복합니다.
- path_flow := 무한대(inf)로 초기화합니다.
- v := sink부터 v != src 인 동안 v := par[v]로 이동하며,
- u := par[v]
- path_flow := path_flow와 temp_graph[u, v] 중 최솟값
- 다시 v := sink부터 v != src 인 동안 v := par[v]로 이동하며,
- u := par[v]
- temp_graph[u, v] := temp_graph[u, v] - path_flow (순방향 간선 용량 감소)
- temp_graph[v, u] := temp_graph[v, u] + path_flow (역방향 잔여 간선 증가)
- 크기가 NODES인 배열 vis를 false로 초기화합니다.
- dfs(temp_graph, src, vis)를 호출하여 소스에서 도달 가능한 노드를 표시합니다.
- i := 0 부터 i < NODES 까지, j := 0 부터 j < NODES 까지 이중 반복하며,
- vis[i]가 true이고 vis[j]가 false이며 graph[i, j]가 0이 아니면
- (i, j)를 최소 컷 간선으로 출력합니다.
- vis[i]가 true이고 vis[j]가 false이며 graph[i, j]가 0이 아니면
- 종료합니다.
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define NODES 6
int bfs(int graph[NODES][NODES], int src, int sink, int par[]) {
bool vis[NODES];
memset(vis, 0, sizeof(vis));
queue <int> que;
que.push(src);
vis[src] = true;
par[src] = -1;
while (!que.empty()) {
int u1 = que.front();
que.pop();
for (int v1=0; v1<NODES; v1++){
if (vis[v1]==false && graph[u1][v1] > 0) {
que.push(v1);
par[v1] = u1;
vis[v1] = true;
}
}
}
return (vis[sink] == true);
}
void dfs(int graph[NODES][NODES], int src, bool vis[]) {
vis[src] = true;
for (int i = 0; i < NODES; i++)
if (graph[src][i] && !vis[i])
dfs(graph, i, vis);
}
void minCut(int graph[NODES][NODES], int src, int sink) {
int u, v;
int temp_graph[NODES][NODES];
for (u = 0; u < NODES; u++)
for (v = 0; v < NODES; v++)
temp_graph[u][v] = graph[u][v];
int par[NODES];
while (bfs(temp_graph, src, sink, par)){
int path_flow = INT_MAX;
for (v=sink; v!=src; v=par[v]) {
u = par[v];
path_flow = min(path_flow, temp_graph[u][v]);
}
for (v=sink; v != src; v=par[v]) {
u = par[v];
temp_graph[u][v] -= path_flow;
temp_graph[v][u] += path_flow;
}
}
bool vis[NODES];
memset(vis, false, sizeof(vis));
dfs(temp_graph, src, vis);
for (int i = 0; i < NODES; i++)
for (int j = 0; j < NODES; j++)
if (vis[i] && !vis[j] && graph[i][j])
cout << "("<< i << ", " << j << ")" << endl;
return;
}
int main() {
int graph1[NODES][NODES] = {
{0, 17, 14, 0, 0, 0},
{0, 0, 11, 13, 0, 0},
{0, 5, 0, 0, 15, 0},
{0, 0, 9, 0, 0, 21},
{0, 0, 0, 8, 0, 5},
{0, 0, 0, 0, 0, 0}
};
minCut(graph1, 0, 5);
}입력
{{0, 17, 14, 0, 0, 0},
{0, 0, 11, 13, 0, 0},
{0, 5, 0, 0, 15, 0},
{0, 0, 9, 0, 0, 21},
{0, 0, 0, 8, 0, 5},
{0, 0, 0, 0, 0, 0}};출력
(1, 3) (4, 3) (4, 5)
동작 원리 요약
이 알고리즘의 핵심은 두 단계로 나눌 수 있습니다. 첫째, BFS로 증가 경로(augmenting path)를 찾아 포드-풀커슨 방식으로 최대 유량을 계산합니다. 둘째, 유량 흐름이 더 이상 없는 잔여 그래프에서 DFS로 소스에서 도달 가능한 노드 집합 S를 구합니다. 그러면 S에 속한 노드에서 S 밖의 노드로 향하는 원본 그래프의 간선들이 바로 최소 s-t 컷이 됩니다. 시간 복잡도는 간선당 최대 유량에 의존하는 포드-풀커슨 방식으로 O(max_flow × E)입니다.