학생마다 가고 싶은 동아리가 몇 개 있고, 동아리마다 한 명만 받는다. 학생을 한 명씩 넣다가 원하는 자리가 이미 차 있으면, 그 자리 주인에게 “다른 데로 옮겨 줄 수 있니?”라고 묻는다. 주인이 또 다른 주인에게 묻는 식으로 연쇄로 비켜 주면 짝이 하나 는다. 먼저 온 사람에게 아무 자리나 주고 끝내면 최대가 안 나올 수 있는데, 이렇게 되물으면 최대가 보장된다. 다만 짝마다 점수가 있어 점수 합을 최대로 하려면 다른 방법(헝가리안 방법)이 필요하다.
예시로 보기
학생 1, 2, 3과 동아리 a, b, c가 있다. 1은 a나 b, 2는 a만, 3은 b나 c를 원한다.
flowchart LR
subgraph L["학생"]
s1["1"]
s2["2"]
s3["3"]
end
subgraph R["동아리"]
ca["a"]
cb["b"]
cc["c"]
end
s1 --- ca
s1 --- cb
s2 --- ca
s3 --- cb
s3 --- cc
선은 “이 학생이 이 동아리를 원한다”이고, 선은 늘 학생 쪽과 동아리 쪽을 잇는다. 2는 a 하나뿐이라 a를 두고 1과 다툰다1.
| 차례 | 한 일 | 짝 |
|---|---|---|
| 학생 1 | a가 비어 있어 a에 넣는다 | 1–a |
| 학생 2 | a는 1의 자리다. 1에게 묻자 1이 b로 옮긴다. 비운 a에 2를 넣는다 | 1–b, 2–a |
| 학생 3 | b는 1의 자리다. 1은 a를 보지만 a는 2의 자리이고, 2는 갈 데가 없다. 1은 못 옮긴다. 3은 다음 후보 c에 들어간다 | 1–b, 2–a, 3–c |
학생 2 차례의 “2 → a → 1 → b”처럼, 빈 학생에서 출발해 “짝이 아닌 간선, 짝인 간선”을 번갈아 밟아 빈 동아리에 닿는 길을 증가 경로라 한다. 이 길 위의 짝을 모두 뒤집으면 짝이 하나 는다.
정의
그래프의 정점이 두 편 L, R로 나뉘고 간선이 늘 L과 R을 잇는다(이분 그래프). 끝점을 공유하지 않는 간선 집합 M을 매칭이라 한다. M에 안 들어간 L의 정점에서 출발해 M에 없는 간선과 M의 간선을 번갈아 밟아 M에 안 들어간 R의 정점에서 끝나는 경로를 증가 경로라 한다.
- 베르주 정리: M이 최대 매칭인 것과 M에 대한 증가 경로가 없는 것은 같다2.
증가 경로가 있으면 그 길 위의 간선을 모두 뒤집어 크기를 1 늘린다. 거꾸로 M보다 큰 매칭 M가 있으면, M과 M에 하나에만 있는 간선들은 번갈아 이어진 경로와 사이클로 나뉜다. 그중 M*의 간선이 하나 더 많은 경로가 있고, 그것이 M의 증가 경로다.
def max_matching(adj, n_right): # adj[u]: 왼쪽 u가 갈 수 있는 오른쪽 정점들
match = [-1] * n_right # 오른쪽 → 짝인 왼쪽
def try_(u, seen):
for v in adj[u]:
if v not in seen:
seen.add(v)
if match[v] == -1 or try_(match[v], seen):
match[v] = u # 증가 경로를 따라 짝을 뒤집는다
return True
return False
return sum(try_(u, set()) for u in range(len(adj)))
왼쪽 정점마다 깊이 우선 탐색으로 증가 경로를 찾는다(쿤의 방법). 한 번 찾을 때 간선을 많아야 한 번씩 보니, 전체는 \(O(VE)\)다. 어떤 왼쪽 정점에서 지금 증가 경로가 없으면 나중에도 없다는 성질이 있어, 왼쪽 정점을 한 번씩만 보면 된다[확인필요: 이 성질의 교재 증명을 확인하지 못했다. 검증 코드의 무작위 비교는 실험으로 확인한 것이다].
활용
- 비용: 쿤의 방법은 \(O(VE)\)다. 정점 수천, 간선 수만이면 충분하다. 더 크면 한 번에 여러 증가 경로를 찾는 호프크로프트–카프 방법을 쓴다.
- 알아보는 신호: “두 무리를 한 명당 하나씩 짝짓는다”, “겹치지 않게 가장 많이 배정한다”.
- 쓰는 곳: 사람과 일 배정, 좌석 배정, 격자에서 겹치지 않게 도미노 놓기.
- 점수가 있는 짝짓기: 짝마다 점수가 있고 점수 합을 최대로 하려면 헝가리안 방법(Hungarian method)을 쓴다. 행과 열에 잠재값을 두고 가장 싸게 늘리는 길로 짝을 하나씩 더하며, \(n \times n\) 표에서 \(O(n^3)\)이다3. 신비로운 유적 탐험의 자식 짝짓기가 이것이다.
- 흔한 실수: seen을 왼쪽 정점마다 새로 만들지 않거나, 반대로 한 탐색 안에서 매번 새로 만들어 같은 자리를 무한히 돈다. 재귀가 깊어지면 파이썬 재귀 한도를 늘려야 한다.
연결
- 선수: 깊이 우선 탐색(DFS), 이분 그래프와 그래프 색칠
- 먼저 온 사람에게 자리를 주는 그리디는 틀린다(확인 문제 C3).
- 두 매칭에 하나에만 있는 간선이 경로와 사이클로 나뉜다는 생각은 스마트한 프로도에서 매칭을 한 단계씩 바꿀 때도 쓴다.
- 연습: 신비로운 유적 탐험
- 두 매칭에 하나에만 있는 간선은 집합의 대칭 차집합 \(M \oplus M^*\)다. 한 점에는 \(M\)의 간선과 \(M^*\)의 간선이 많아야 하나씩 닿는다. 그래서 \(M \oplus M^*\)에서는 점마다 간선이 둘 이하이고 두 매칭의 간선이 번갈아 이어져, 경로와 사이클로만 나뉜다. 증가 경로 \(P\)를 따라 짝을 뒤집는 일도 \(M\)을 \(M \oplus P\)로 바꾸는 것이다.
- 몇몇 학생이 원하는 자리를 모두 모아도 그 학생 수보다 적으면, 그 학생들을 모두 짝지을 수는 없다. 학생마다 다른 자리를 줘야 하는데, 학생이 자리보다 많으면 비둘기집 원리로 어떤 자리에 두 명이 겹치기 때문이다.
확인 문제
C1 예시에서 학생 3이 b만 원한다면, 학생 3 차례에 무슨 일이 생기고 최대 짝은 몇 쌍인가?
답: b는 1의 자리라 1에게 묻는다. 1은 a를 보지만 a는 2의 자리이고 2는 a 말고 갈 데가 없다. 그래서 1은 못 옮기고 3은 짝을 못 얻는다. 최대는 2쌍이다. a, b 두 자리에 세 학생이 몰리니 3쌍은 불가능하다.
C2 코드의 try_(u, seen)이 하는 일을 한 문장으로 말하라.
답: 왼쪽 u에서 출발하는 증가 경로를 찾아, 찾으면 그 길 위의 짝을 뒤집어 u에게 짝을 만들어 주고 True를 돌려준다. seen은 한 번의 찾기에서 같은 오른쪽 정점을 두 번 보지 않게 막는다.
C3 “학생 차례대로 아직 빈 동아리 중 첫 번째에 넣고 다시 바꾸지 않는다”가 최대를 못 내는 예를 들어라.
답: 학생 1은 a나 b, 학생 2는 a만 원한다. 1이 먼저 a를 가져가면 2는 갈 데가 없어 1쌍이다. 1을 b로 보내면 2쌍이다. 되묻기(증가 경로)가 없으면 이런 경우를 놓친다.
-
예시로 보기의 학생 1, 2, 3과 동아리 a, b, c의 희망 관계를 이분 그래프로 그렸다. ↩
-
Cormen 외, Introduction to Algorithms 3판, 26.3 “Maximum bipartite matching”은 매칭을 최대 흐름으로 바꿔 구한다. 증가 경로로 최대 매칭을 판정하는 성질은 베르주(C. Berge, 1957)의 정리로 알려져 있다. Laaksonen, Competitive Programmer’s Handbook (2018판), 20.3 “Maximum matchings”도 흐름으로 구한다. ↩
-
Kuhn, “The Hungarian method for the assignment problem”, Naval Research Logistics Quarterly 2 (1955). \(O(n^3)\) 구현은 잠재값을 쓰는 널리 알려진 판이고, 검증 코드에서 순열 전부와 비교했다. ↩