21. 이분매칭
Bipartite matching, 두 집단(집합) 간 1:1대응(혹은 조건 상 최대로 효율적인 연결관계)을 구현하는 알고리즘을 의미한다.
네트워크 플로우와 연계되는 개념이며, graph 상에서 같은 집합끼리는 연결되지 않은 상태에서 1:1대응하는 경우를 일컫는다.
21-1. 이분매칭의 핵심
이분매칭은 각 집단을 가장 효과적으로 매칭한다는 것, 즉 모든 노드들이 다른 집단의 노드들을 연결하는 최대 매칭을 의미한다.
21-2. 이분매칭 과정
최초 graph 상태가 위와 같다고 가정하자.
왼쪽에서 출발하는 노드를 정할 떄는 DFS를 이용한다.
- 왼쪽 2가 오른쪽 1을 선택할때, 왼쪽 1은 비어있는 노드들 중 2를 선택한다.
- 그 후 왼쪽 3이 오른쪽 2를 선택하려고 할때, 왼쪽 1은 비어있는 노드인 3을 선택한다.
최종적으로 연결된 상태는 아래 grapgh 형태이다.
