네트워크 유량 (Network Flow)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 5분 · 1,391자/단어 #algorithm #graph #flow #max-flow #ford-fulkerson #edmonds-karp #dinic

정의

네트워크 유량 (Network Flow) 은 방향 그래프 G = (V, E) 에서 각 간선 (u, v) 의 용량 (capacity) c(u, v) 가 주어질 때, 소스 s 에서 싱크 t 로 흐를 수 있는 최대 유량 (max flow) 을 구하는 문제.

제약:

용량 제약 (capacity constraint): 각 간선의 유량 f(u, v) ≤ c(u, v).
유량 보존 (flow conservation): s, t 제외 모든 정점에서 들어오는 유량 = 나가는 유량.

가장 유명한 알고리즘: Ford-Fulkerson (개념), Edmonds-Karp (O(VE^2)), Dinic (O(V^2 E)).

문제 상황과 동기

“파이프 네트워크에서 최대로 보낼 수 있는 물의 양”, “교통망 최대 수송량”, “이분 매칭 (bipartite matching)”, “최소 컷 (min-cut)” 모두 유량으로 모델링.

naive: 모든 경로 나열 O(2^E). 핵심 통찰: 증가 경로 (augmenting path) 를 반복. 남은 용량 (residual capacity) 가 있는 s → t 경로를 찾아 유량을 밀어 넣으면, 최종적으로 최대 유량 수렴. max-flow min-cut theorem: 최대 유량 = 최소 컷.

PS: “매칭 개수”, “분리 집합”, “비용 + 유량 (MCMF)”, BOJ 이분 매칭 대부분.

시각화

핵심 아이디어

residual graph

원 그래프 G 와 현재 유량 f 에서, 잔여 그래프 (residual graph) G_f:

간선 (u, v) 가 c(u, v) - f(u, v) > 0 이면 (u, v) 간선 추가 (forward edge).
f(u, v) > 0 이면 (v, u) 간선 추가, 용량 = f(u, v) (backward edge).

증가 경로: G_f 에서 s → t 경로. 경로 용량 = min(residual capacity).

Ford-Fulkerson 반복

f = 0
while exists augmenting path p in G_f:
    push flow along p
    update f and G_f
return f

증가 경로를 어떻게 찾느냐에 따라 복잡도 다름.

Edmonds-Karp (BFS)

증가 경로를 BFS 로. 가장 짧은 경로 우선 → O(VE) 번 반복, 각 BFS O(E) → O(VE^2).

Dinic (level graph + blocking flow)

level graph: BFS 로 s 에서 거리 d[v] 계산.
blocking flow: d[u] + 1 = d[v] 인 간선만 DFS. 한 번에 여러 경로 동시 처리.
반복: level graph 재구성 → blocking flow. 총 O(V) 번 → O(V^2 E).

알고리즘

Edmonds-Karp(G, s, t):
    for each edge (u, v):
        f[u][v] = 0
    while true:
        path, bottleneck = BFS_augment(G_f, s, t)
        if path is null: break
        for (u, v) in path:
            f[u][v] += bottleneck
            f[v][u] -= bottleneck
    return sum of f[s][v] for all v

BFS_augment(G_f, s, t):
    parent = [-1] * V
    queue = [s]
    while queue not empty:
        u = queue.pop(0)
        for v in adj[u]:
            if parent[v] == -1 and residual[u][v] > 0:
                parent[v] = u
                queue.append(v)
                if v == t:
                    path = trace(parent, s, t)
                    bottle = min(residual[u][v] for (u,v) in path)
                    return path, bottle
    return null, 0

구현

// Edmonds-Karp: O(VE^2)
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int n, cap[105][105], flow[105][105];

int bfs(int s, int t, vector<int>& parent) {
  fill(parent.begin(), parent.end(), -1);
  parent[s] = s;
  queue<pair<int,int>> q; q.push({s, INF});
  while (!q.empty()) {
      auto [u, f] = q.front(); q.pop();
      if (u == t) return f;
      for (int v = 0; v < n; v++) {
          int res = cap[u][v] - flow[u][v];
          if (parent[v] == -1 && res > 0) {
              parent[v] = u;
              int nf = min(f, res);
              q.push({v, nf});
          }
      }
  }
  return 0;
}

int maxFlow(int s, int t) {
  int total = 0;
  vector<int> parent(n);
  while (int pushed = bfs(s, t, parent)) {
      total += pushed;
      int v = t;
      while (v != s) {
          int u = parent[v];
          flow[u][v] += pushed;
          flow[v][u] -= pushed;
          v = u;
      }
  }
  return total;
}

int main() {
  int m, s, t; cin >> n >> m >> s >> t;
  for (int i = 0; i < m; i++) {
      int u, v, c; cin >> u >> v >> c;
      cap[u][v] += c;
  }
  cout << maxFlow(s, t) << "\n";
}

# Edmonds-Karp max flow
from collections import deque
import sys
input = sys.stdin.readline

def bfs(s, t, parent, cap, flow, n):
  parent[:] = [-1] * n
  parent[s] = s
  q = deque([(s, float('inf'))])
  while q:
      u, f = q.popleft()
      if u == t:
          return f
      for v in range(n):
          res = cap[u][v] - flow[u][v]
          if parent[v] == -1 and res > 0:
              parent[v] = u
              nf = min(f, res)
              q.append((v, nf))
  return 0

def max_flow(n, s, t, cap):
  flow = [[0]*n for _ in range(n)]
  parent = [-1] * n
  total = 0
  while True:
      pushed = bfs(s, t, parent, cap, flow, n)
      if pushed == 0:
          break
      total += pushed
      v = t
      while v != s:
          u = parent[v]
          flow[u][v] += pushed
          flow[v][u] -= pushed
          v = u
  return total

n, m, s, t = map(int, input().split())
cap = [[0]*n for _ in range(n)]
for _ in range(m):
  u, v, c = map(int, input().split())
  cap[u][v] += c
print(max_flow(n, s, t, cap))

// Edmonds-Karp in Java
import java.util.*;
import java.io.*;
public class Main {
  static int n, cap[][], flow[][];
  static final int INF = (int)1e9;

  static int bfs(int s, int t, int[] parent) {
      Arrays.fill(parent, -1);
      parent[s] = s;
      Queue<int[]> q = new LinkedList<>();
      q.add(new int[]{s, INF});
      while (!q.isEmpty()) {
          int[] cur = q.poll();
          int u = cur[0], f = cur[1];
          if (u == t) return f;
          for (int v = 0; v < n; v++) {
              int res = cap[u][v] - flow[u][v];
              if (parent[v] == -1 && res > 0) {
                  parent[v] = u;
                  int nf = Math.min(f, res);
                  q.add(new int[]{v, nf});
              }
          }
      }
      return 0;
  }

  static int maxFlow(int s, int t) {
      int total = 0;
      int[] parent = new int[n];
      while (true) {
          int pushed = bfs(s, t, parent);
          if (pushed == 0) break;
          total += pushed;
          for (int v = t; v != s; v = parent[v]) {
              int u = parent[v];
              flow[u][v] += pushed;
              flow[v][u] -= pushed;
          }
      }
      return total;
  }

  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int s = Integer.parseInt(st.nextToken());
      int t = Integer.parseInt(st.nextToken());
      cap = new int[n][n]; flow = new int[n][n];
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          int c = Integer.parseInt(st.nextToken());
          cap[u][v] += c;
      }
      System.out.println(maxFlow(s, t));
  }
}

stdin

결과

복잡도

알고리즘	시간	공간
Ford-Fulkerson	O(E · max_flow), 정수 용량시 pseudo-polynomial	O(V^2)
Edmonds-Karp	O(V E^2)	O(V^2)
Dinic	O(V^2 E), 이분 그래프면 O(E √V)	O(V^2)
Push-Relabel	O(V^3), 실제 빠름	O(V^2)

변형 / 활용

1. 이분 매칭 (bipartite matching)

왼쪽 그룹 L, 오른쪽 R. s → L (용량 1), R → t (용량 1), L-R 간선 (용량 1). max flow = 최대 매칭.

2. 최소 컷 (min-cut)

max-flow min-cut theorem: 최대 유량 = 최소 컷. BFS 로 s 에서 도달 가능 정점 집합 S, 나머지 T. cut = 간선 (u, v) where u ∈ S, v ∈ T.

3. 비용 유량 (MCMF, Min-Cost Max-Flow)

각 간선에 비용. 최대 유량 중 최소 비용 경로. SPFA / Dijkstra + 유량.

4. 다중 소스/싱크

여러 소스 s_i, 싱크 t_j. super-source S → s_i (INF), t_j → super-sink T (INF).

함정

1. 양방향 간선

무방향 간선 (u, v) 는 (u, v), (v, u) 두 방향 각각 cap 추가.

2. 역방향 간선 초기화

flow[v][u] = -flow[u][v]. 초기 0.

3. 정수 용량 가정

Ford-Fulkerson 은 무리수 용량이면 무한 루프 가능. Edmonds-Karp / Dinic 은 OK.

4. overflow

용량 합이 int 범위 넘으면 long long.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 6086	최대 유량	-	kokoa-lab
BOJ 2188	축사 배정 (이분 매칭)	-	kokoa-lab
BOJ 11375	열혈강호	-	kokoa-lab
BOJ 17412	도시 왕복하기 1	-	kokoa-lab

참고

이 글의 용어 (4개)

너비 우선 탐색 (BFS)algorithm: 정의 너비 우선 탐색 (Breadth-First Search, BFS) 는 그래프 G=(V, E) 에서 시작 정점 s 로부터 가까운 정점부터 순서대로 방문하는 알고리즘. 큐 (F…
이분 매칭 (Bipartite Matching)algorithm: 정의 이분 매칭 (Bipartite Matching) 은 이분 그래프 G = (L ∪ R, E) 에서 간선 부분집합 M ⊆ E 을 선택하되, M 의 어떤 두 간선도 정점을 공유하…
최대 유량 최소 컷 정리 (Max-Flow Min-Cut Theorem)algorithm: 정의 최대 유량 최소 컷 정리 (Max-Flow Min-Cut Theorem) 는 네트워크 유량 그래프 G = (V, E) 에서 source s 에서 sink t 로의 최대 유량…
최소 비용 최대 유량 (Min-Cost Max-Flow, MCMF)algorithm: 정의 최소 비용 최대 유량 (Min-Cost Max-Flow, MCMF) 은 각 간선에 용량(capacity)과 단위 비용(cost)이 주어질 때, 최대 유량을 달성하는 여러 방…