이분 매칭1 [알고리즘] 이분 매칭(Bipartite Matching) 1. 이분 매칭 네트워크 플로우(Network Flow) 알고리즘에서 두 정점 사이의 용량이 1이고, 정점이 두 집합으로 구분되는 특수한 경우. 한쪽 그룹을 X, 다른 그룹을 Y라고 할 때, X → Y로의 최대 유량을 구하는 문제. 이때, 각 용량이 1이므로 최대 매칭 수를 찾는 문제로 볼 수 있음. 2. 알고리즘 예시 DFS를 활용하여, 매칭을 하나씩 선택하는 과정을 거친다. 예시는 조금 복잡하지만, 백준 문제의 예시를 가져왔다. 세부적인 예시는 아래와 같다. 다음과 같이 왼쪽 그룹, 오른쪽 그룹에 있는 정점에 대하여 각 선분 중 연결되어 있다. DFS를 응용하여 편하게 최적의 답을 찾을 수 있다. 우선 1번점에서 연결할 수 있는 최적의 점을 찾는다. 그러면, 왼쪽 1번점, 오른쪽 2번점을 연결할 수 .. 2022. 5. 22. 이전 1 다음
