네트워크 플로우와 최대 유량 알고리즘

개요

네트워크 플로우는 소스(source)에서 싱크(sink)로 최대한 많은 유량(flow)을 보내는 문제입니다. 각 간선에는 용량(capacity) 제약이 있습니다. 최대 유량(Maximum Flow)은 이분 매칭, 프로젝트 스케줄링, 경로 차단 문제 등으로 환원됩니다.

1. 기본 개념

그래프 G = (V, E)
- 소스 s: 유량 출발
- 싱크 t: 유량 도착
- 용량 c(u,v): 간선 (u,v)의 최대 유량
- 유량 f(u,v): 실제 흐르는 유량

조건:
1. 용량 제약: 0 ≤ f(u,v) ≤ c(u,v)
2. 유량 보존: 각 노드에서 유입량 = 유출량 (s, t 제외)

목표: s에서 t로 보낼 수 있는 최대 유량

2. Ford-Fulkerson — O(E × max_flow)

#include <vector>
#include <queue>
#include <climits>

class MaxFlow {
    int n;
    std::vector<std::vector<int>> cap; // 잔여 용량
    std::vector<std::vector<int>> adj; // 인접 리스트

public:
    explicit MaxFlow(int n) : n(n), cap(n, std::vector<int>(n, 0)), adj(n) {}

    void AddEdge(int u, int v, int capacity) {
        cap[u][v] += capacity;
        // 역방향 간선 (잔여 그래프)
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // BFS로 증가 경로 탐색 (Edmonds-Karp)
    int BFS(int s, int t, std::vector<int>& parent) {
        std::fill(parent.begin(), parent.end(), -1);
        parent[s] = s;
        std::queue<std::pair<int,int>> q;
        q.push({s, INT_MAX});

        while (!q.empty()) {
            auto [u, flow] = q.front(); q.pop();

            for (int v : adj[u]) {
                if (parent[v] == -1 && cap[u][v] > 0) {
                    parent[v] = u;
                    int newFlow = std::min(flow, cap[u][v]);
                    if (v == t) return newFlow;
                    q.push({v, newFlow});
                }
            }
        }
        return 0;
    }

    int MaxFlowCalc(int s, int t) {
        int totalFlow = 0;
        std::vector<int> parent(n);
        int newFlow;

        while ((newFlow = BFS(s, t, parent)) > 0) {
            totalFlow += newFlow;

            // 경로상 잔여 용량 업데이트
            int curr = t;
            while (curr != s) {
                int prev = parent[curr];
                cap[prev][curr] -= newFlow;
                cap[curr][prev] += newFlow; // 역방향 증가
                curr = prev;
            }
        }

        return totalFlow;
    }
};

3. Dinic 알고리즘 — O(V² × E)

class DinicFlow {
    struct Edge { int to, rev; int cap; };

    int n;
    std::vector<std::vector<Edge>> graph;
    std::vector<int> level, iter;

    bool BFS(int s, int t) {
        level.assign(n, -1);
        std::queue<int> q;
        level[s] = 0;
        q.push(s);

        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (const Edge& e : graph[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }

    int DFS(int v, int t, int f) {
        if (v == t) return f;

        for (int& i = iter[v]; i < (int)graph[v].size(); i++) {
            Edge& e = graph[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                int d = DFS(e.to, t, std::min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

public:
    explicit DinicFlow(int n) : n(n), graph(n), level(n), iter(n) {}

    void AddEdge(int from, int to, int cap) {
        graph[from].push_back({to, (int)graph[to].size(), cap});
        graph[to].push_back({from, (int)graph[from].size()-1, 0});
    }

    int MaxFlowCalc(int s, int t) {
        int flow = 0;
        while (BFS(s, t)) {
            iter.assign(n, 0);
            int d;
            while ((d = DFS(s, t, INT_MAX)) > 0) flow += d;
        }
        return flow;
    }
};

4. 알고리즘 복잡도 비교

알고리즘	복잡도	적합한 경우
Ford-Fulkerson	O(E × max_f)	소규모, 정수 유량
Edmonds-Karp	O(V × E²)	일반적 사용
Dinic	O(V² × E)	대규모, 실용적 최선

5. 최소 컷 — 최대 유량 정리

Max-Flow Min-Cut 정리:
최대 유량 = 최소 컷의 용량

최소 컷: 소스와 싱크를 분리하는 간선 집합 중 최소 용량
→ 네트워크 병목 구간 파악에 활용

// 최대 유량 계산 후 잔여 그래프에서 최소 컷 찾기
void FindMinCut(int s, std::vector<std::pair<int,int>>& cutEdges) {
    // BFS로 s에서 도달 가능한 노드 집합 S 찾기
    std::vector<bool> visited(n, false);
    std::queue<int> q;
    visited[s] = true;
    q.push(s);

    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u = 0; u < n; u++) {
            if (!visited[u] && cap[v][u] > 0) {
                visited[u] = true;
                q.push(u);
            }
        }
    }

    // S에서 (V-S)로 가는 간선이 최소 컷
    for (int u = 0; u < n; u++)
        if (visited[u])
            for (int v = 0; v < n; v++)
                if (!visited[v] && originalCap[u][v] > 0)
                    cutEdges.push_back({u, v});
}

6. 이분 매칭

// 이분 그래프에서 최대 매칭
// 네트워크 플로우로 변환: 소스→좌측, 우측→싱크, 모든 용량 1
int BipartiteMatching(int leftN, int rightN,
    const std::vector<std::pair<int,int>>& edges)
{
    MaxFlow flow(leftN + rightN + 2);
    int src = leftN + rightN, snk = src + 1;

    for (int i = 0; i < leftN; i++)
        flow.AddEdge(src, i, 1);

    for (const auto& [u, v] : edges)
        flow.AddEdge(u, leftN + v, 1);

    for (int i = 0; i < rightN; i++)
        flow.AddEdge(leftN + i, snk, 1);

    return flow.MaxFlowCalc(src, snk);
}

7. 게임 개발 활용

// 맵에서 경로 차단을 위한 최소 간선 제거
// 최소 컷 = 최소한의 경로 차단 지점

// 자원 배분: 여러 공장(소스)에서 여러 도시(싱크)로 최대 공급량
int ResourceAllocation(
    const std::vector<Factory>& factories,
    const std::vector<City>& cities,
    const std::vector<Road>& roads)
{
    DinicFlow flow(factories.size() + cities.size() + 2);
    // 슈퍼 소스와 슈퍼 싱크로 연결
    // 각 공장 용량과 도로 용량 설정
    return flow.MaxFlowCalc(superSrc, superSnk);
}

정리

Ford-Fulkerson: 증가 경로 반복 탐색
Edmonds-Karp: BFS 기반 → O(V × E²)
Dinic: 레벨 그래프 + 블로킹 플로우 → O(V² × E), 실용적 최선
Max-Flow = Min-Cut (병목 구간 파악)
이분 매칭, 프로젝트 스케줄링으로 환원 가능

네트워크 플로우와 최대 유량 알고리즘

개요

1. 기본 개념

2. Ford-Fulkerson — O(E × max_flow)

3. Dinic 알고리즘 — O(V² × E)

4. 알고리즘 복잡도 비교

5. 최소 컷 — 최대 유량 정리

6. 이분 매칭

7. 게임 개발 활용

정리

참고 자료