이분매칭

이분 매칭(Bipartite Matching)

이전 게시글인 에 이어지는 알고리즘 개념 글입니다 https://codingsmu.tistory.com/109 이분 매칭(Bipartite Matching)이란? 네트워크 플로우의 개념중에서 이분 그래프(Bipartite Graph)에서의 최대 유량(maximum flow)을 구하는 경우로, 에지의 용량(capacity)이 전부 1인 이분 그래프에서의 최대유량(maximum flow)을 구하는 문제는 이분 그래프에서의 최대 매칭(maximium matching)과 동치이다. 이때 매칭은, 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미로 이분그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉 혹은 에드몬드 카프 알고리즘을 이용해 구해줄 수 있으나, DFS를 이용하여 O(V*E)시간에 쉽게 구현할 수 있다..