Algorithm
[Python] 이분 매칭 알고리즘(Bipartite Matching)
이분 매칭 알고리즘은 유량 그래프의 특수한 형태이다. 유량 그래프는 다음 포스팅에서 다루기로 하고... 이분 매칭 알고리즘에 대해 알아보자. 이분 매칭 알고리즘을 알아보기 전에, 이분 그래프에 대해 먼저 알고 넘어가야 한다. 이분 그래프란 정점을 두 개의 그룹으로 나누었을 때, 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 말한다. 위의 그림에서 보면 파란색 노드의 집합을 X, 빨간색 노드의 집합을 Y로 표현할 수 있고, 따라서 위의 그래프는 이분 그래프이다. 이분 매칭 알고리즘은 위와 같은 이분 그래프에서 최대 매칭의 개수를 찾는 것과 같다. 매칭이란 간선 하나를 선택하는 것을 말하는데, 예를 들어 그림에서 A와 a를 연결하는 간선을 선택하면 (A, a)라는 매칭이 생기는 것이다..
