이분 매칭 — 두 그룹을 최적으로 짝짓기
직원 5명에게 업무 5개를 배정해야 하는데, 각자 할 수 있는 업무가 다릅니다. 어떻게 하면 가장 많은 업무를 배정할 수 있을까요?
개념 정의
이분 매칭은 이분 그래프에서 최대한 많은 쌍을 연결하는 문제 입니다. 이분 그래프란 정점을 두 그룹(A, B)으로 나눴을 때, 같은 그룹 내의 정점끼리는 간선이 없는 그래프를 말합니다.
예를 들어 직원 그룹과 업무 그룹이 있고, 각 직원이 수행 가능한 업무가 간선으로 연결되어 있다면, 최대 매칭은 최대한 많은 직원-업무 쌍을 만드는 것입니다.
왜 필요한가
이분 매칭은 생각보다 다양한 곳에서 쓰입니다.
- **작업 스케줄링 **: 서버에 작업을 배정할 때, 각 서버가 처리할 수 있는 작업 유형이 다르다면 최적 배정이 필요합니다
- ** 추천 시스템 **: 사용자-상품 매칭
- ** 네트워크 라우팅 **: 송신자-수신자 쌍의 최적 연결
- ** 테스트 배정 **: CI/CD에서 테스트를 러너에 분배할 때
이분 그래프 판별
먼저 주어진 그래프가 이분 그래프인지 확인해야 합니다. BFS로 2-색 칠하기를 시도하면 됩니다.
// 이분 그래프 판별 — BFS 2-색칠
public boolean isBipartite(List<List<Integer>> graph, int n) {
int[] color = new int[n];
Arrays.fill(color, -1); // 미방문
for (int start = 0; start < n; start++) {
if (color[start] != -1) continue;
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
color[start] = 0;
while (!queue.isEmpty()) {
int curr = queue.poll();
for (int next : graph.get(curr)) {
if (color[next] == -1) {
color[next] = 1 - color[curr]; // 반대 색
queue.offer(next);
} else if (color[next] == color[curr]) {
return false; // 같은 색이면 이분 그래프 아님
}
}
}
}
return true;
}
핵심 아이디어는 간단합니다. 인접한 정점을 서로 다른 색으로 칠하다가, 이미 같은 색으로 칠해진 정점을 만나면 이분 그래프가 아닌 것입니다. 홀수 길이의 사이클이 있으면 이분 그래프가 될 수 없습니다.
동작 원리 — 헝가리안 알고리즘
헝가리안 알고리즘(Kuhn's Algorithm)은 가장 직관적인 이분 매칭 알고리즘입니다.
핵심 개념: 증가 경로
** 증가 경로(augmenting path)**란 매칭되지 않은 정점에서 시작하여, 매칭 간선과 비매칭 간선이 번갈아 나타나고, 매칭되지 않은 정점에서 끝나는 경로입니다.
증가 경로를 찾으면 경로상의 매칭/비매칭을 뒤집어서 매칭 크기를 1 늘릴 수 있습니다.
알고리즘 흐름
- 왼쪽 그룹의 각 정점에 대해 DFS로 증가 경로를 찾습니다
- 증가 경로를 찾으면 경로를 뒤집어 매칭을 갱신합니다
- 더 이상 증가 경로가 없으면 현재 매칭이 최대 매칭입니다
public class HungarianMatching {
private List<List<Integer>> graph; // 왼쪽 → 오른쪽 간선
private int[] match; // match[오른쪽] = 매칭된 왼쪽 정점 (-1이면 미매칭)
private boolean[] visited;
public int maxMatching(List<List<Integer>> graph, int leftSize, int rightSize) {
this.graph = graph;
this.match = new int[rightSize];
Arrays.fill(match, -1);
int result = 0;
for (int left = 0; left < leftSize; left++) {
visited = new boolean[rightSize];
if (dfs(left)) {
result++;
}
}
return result;
}
// 왼쪽 정점 u에서 증가 경로를 찾는 DFS
private boolean dfs(int u) {
for (int v : graph.get(u)) {
if (visited[v]) continue;
visited[v] = true;
// v가 미매칭이거나, v에 매칭된 정점에서 다른 경로를 찾을 수 있으면
if (match[v] == -1 || dfs(match[v])) {
match[v] = u;
return true;
}
}
return false;
}
}
dfs(match[v])가 핵심입니다. v가 이미 매칭되어 있어도, 매칭 상대인 match[v]가 다른 상대를 찾을 수 있다면 자리를 양보하는 것입니다.
Hopcroft-Karp 알고리즘
헝가리안의 시간 복잡도는 O(V × E)인데, 정점이 많아지면 느릴 수 있습니다. Hopcroft-Karp는 이를 O(E√V) 로 개선합니다.
아이디어
한 번에 하나의 증가 경로를 찾는 대신, BFS로 같은 길이의 최단 증가 경로를 한꺼번에 찾아서 동시에 적용합니다.
public class HopcroftKarp {
private List<List<Integer>> graph;
private int[] matchL, matchR; // 왼쪽/오른쪽 매칭 정보
private int[] dist; // BFS 거리
private int leftSize, rightSize;
private static final int NIL = -1;
public int maxMatching(List<List<Integer>> graph, int leftSize, int rightSize) {
this.graph = graph;
this.leftSize = leftSize;
this.rightSize = rightSize;
matchL = new int[leftSize];
matchR = new int[rightSize];
dist = new int[leftSize];
Arrays.fill(matchL, NIL);
Arrays.fill(matchR, NIL);
int result = 0;
// BFS로 증가 경로가 있는 동안 반복
while (bfs()) {
for (int u = 0; u < leftSize; u++) {
if (matchL[u] == NIL && dfs(u)) {
result++;
}
}
}
return result;
}
// 최단 증가 경로의 길이를 구하는 BFS
private boolean bfs() {
Queue<Integer> queue = new LinkedList<>();
for (int u = 0; u < leftSize; u++) {
if (matchL[u] == NIL) {
dist[u] = 0;
queue.offer(u);
} else {
dist[u] = Integer.MAX_VALUE;
}
}
boolean found = false;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph.get(u)) {
int w = matchR[v]; // v에 매칭된 왼쪽 정점
if (w == NIL) {
found = true; // 증가 경로 발견
} else if (dist[w] == Integer.MAX_VALUE) {
dist[w] = dist[u] + 1;
queue.offer(w);
}
}
}
return found;
}
// 최단 증가 경로를 따라 매칭 갱신
private boolean dfs(int u) {
for (int v : graph.get(u)) {
int w = matchR[v];
if (w == NIL || (dist[w] == dist[u] + 1 && dfs(w))) {
matchL[u] = v;
matchR[v] = u;
return true;
}
}
dist[u] = Integer.MAX_VALUE;
return false;
}
}
시간 복잡도 비교
| 알고리즘 | 시간 복잡도 | 특징 |
|---|---|---|
| 헝가리안 (Kuhn) | O(V × E) | 구현이 간단, 소규모에 적합 |
| Hopcroft-Karp | O(E√V) | 대규모 그래프에 효율적 |
백엔드/실무 연결
작업 스케줄링
서버 팜에서 각 서버가 처리할 수 있는 작업 유형이 다를 때, 이분 매칭으로 최적 배정을 할 수 있습니다. Kubernetes의 Pod 스케줄링에서 노드 어피니티(node affinity) 설정도 비슷한 개념입니다.
데이터베이스 조인 최적화
쿼리 옵티마이저가 여러 테이블의 조인 순서를 결정할 때, 내부적으로 매칭 알고리즘의 변형을 활용하는 경우가 있습니다.
CI/CD 테스트 분배
테스트 스위트를 여러 러너에 분배할 때, 각 러너의 능력(OS, 환경)에 맞게 테스트를 배정하는 것도 이분 매칭 문제입니다.
쾨닉의 정리
이분 그래프에서 ** 최대 매칭 = 최소 정점 커버 **라는 쾨닉의 정리가 있습니다. 이를 활용하면 "최소한의 서버로 모든 요청 유형을 커버하려면 몇 대가 필요한가?" 같은 문제도 풀 수 있습니다.
최대 매칭 크기 = 최소 정점 커버 크기
최대 독립 집합 크기 = 전체 정점 수 - 최대 매칭 크기
주의할 점
증가 경로를 찾을 때 이미 시도한 매칭을 되돌리지 않는 실수
헝가리안 알고리즘에서 증가 경로를 찾으면, 경로 상의 매칭/비매칭 간선을 ** 뒤집어야** 합니다. 이 과정을 빠뜨리면 매칭 수가 늘어나지 않습니다.
이분 그래프인지 확인하지 않고 알고리즘을 적용하는 실수
이분 매칭은 이분 그래프에서만 의미가 있습니다. 그래프가 이분 그래프인지 먼저 BFS/DFS 2-coloring으로 확인해야 합니다.
정리
- ** 이분 그래프 **: 정점을 두 그룹으로 나눠 같은 그룹 내 간선이 없는 그래프, BFS 2-색칠로 판별합니다
- ** 이분 매칭 **: 두 그룹 사이에서 최대한 많은 쌍을 만드는 문제입니다
- ** 헝가리안 알고리즘 **: DFS로 증가 경로를 하나씩 찾는 O(V × E) 알고리즘입니다
- Hopcroft-Karp: BFS + DFS로 증가 경로를 한꺼번에 찾는 O(E√V) 알고리즘입니다
- ** 증가 경로 **가 핵심 개념입니다. 매칭/비매칭 간선을 뒤집어 매칭 크기를 1 늘리는 경로입니다
- 작업 스케줄링, 리소스 배정 등 실무에서도 활용할 수 있는 패턴입니다