[알고리즘] 이분 매칭(Bipartite Matching) 알아보기

 최근 배우게 된 알고리즘 중 가장 실생활과 밀접한 관련이 있다고 느껴지는 알고리즘이다. (이미 내가 사용하고 있을 수도 있지만) 이름을 알고 있는 알고리즘이 아직 그다지 많지 않은데, 열심히 공부해서 얼른 수를 늘리고 싶다. 문제를 해결할 때 필요한 알고리즘을 적재적소에 떠올리고 싶은데 지식이 부족하다. 그래도 과거의 나보단 낫다는 것에 항상 의의를 두려고 노력 중.

---

 이분 매칭(Bipartite Matching)

이분 매칭(Bipartite Maching)

 이분 매칭은 네크워크 플로우(Network flow)에서 등장하는 개념 중 하나이다. 그렇지만 네트워크 플로우를 처음 들어 본다고 하더라도 쉽게 이해할 수 있다. 이분 매칭은 이분 그래프에서 한 그룹의 정점에서 다른 그룹의 정점으로 간선을 연결할 때 각각이 일대일 대응으로 매칭되는 것을 의미한다. 주로 이분 그래프에서의 최대 유량을 구하는 데에 쓰인다지만 이렇게만 보면 단어도 좀 어려워 보이고 무슨 말인지 잘 모르겠다. 우선 이분 그래프가 무엇인지에 대해 살펴보고 이걸 쉽게 풀어 설명해 보겠다.

---

이분 그래프(Bipartite Graph)

 

 위의 그래프는 모두 이분 그래프이다. 이분 그래프란 정점을 두 개의 그룹으로 나누었을 때 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 말한다. 그래프의 정점이 두 그룹으로 나누어지고, 서로 다른 그룹의 정점들만 간선으로 연결되어져 있는, 즉 같은 그룹의 정점들끼리는 연결되지 않는 형태의 그래프라고 할 수 있다. 이제 이걸 알고 다시 이분 매칭의 설명을 보자.

 

 "이분 매칭은 이분 그래프에서 한 그룹의 정점에서 다른 그룹의 정점으로 간선을 연결할 때 각각이 일대일 대응으로 매칭되는 것을 의미한다."  

 

 즉, 이분 매칭은 이분 그래프에서 한 그룹의 정점에서 다른 그룹의 정점으로 간선을 연결할 때 하나의 간선으로만 연결되는 것을 의미하는 셈이다. 위에서 이분 매칭은 이분 그래프에서의 최대 유량을 구하는 데에 주로 쓰인다고 했다. 이건 무엇을 의미할까? 최대 유량이라는 말에서 대충 짐작할 수 있는데, 간단히 말하자면 두 그룹의 정점들을 최대한 많이 연결해 주는 데에 쓰이는 것이다. 다시 한 번 첫 번째 그림을 보자.

 

 이 그림에서 가장 두 그룹의 정점을 가장 많이 연결해 주려면 어떻게 연결해 주어야 할까? 1번 노드가 처음으로 연결할 수 있는 다른 그룹의 정점은 4번이다. 하지만 그렇게 연결하면 2번 노드는 갈 곳이 없어지고, 3번 노드는 5번 노드와 연결되어 총 네 개의 노드만을 연결하게 된다. 하지만 1번 노드를 5번 노드에, 2번 노드를 4번 노드에, 3번 노드를 6번 노드에 연결해 주면 모든 노드들을 연결할 수 있다. 이를 가능하게 하는 알고리즘에는 여러 종류가 있는데, 그중에서 DFS로 구현이 가능하다. 1번 노드에서 DFS를 시작하면 처음에는 4번 노드와 연결될 것이다. 그리고 2번 노드로 DFS를 하고 나면 또 4번 노드가 등장하는데, 이때 4번 노드와 매칭된 노드(=1번 노드)에 DFS를 실행했을 때 만약 다른 노드와 연결될 수 있다면 그 노드와 연결해 주고 2번 노드는 4번 노드와 연결해 주면 된다. 이를 반복하면 두 그룹의 정점을 최대한 많이 연결해 줄 수 있다.

---

 Related

2019/07/09 - [코학/알고리즘] - [알고리즘] DFS와 BFS에 대해 알아보기

2019/08/23 - [코학/문제] - [백준/BOJ/C언어] 11375번 :: 열혈강호

---

 사실 설명 후에 문제에 직접 적용해서 구현한 걸 보는 게 가장 이해하기 좋은데, 글이 너무 길어질 것 같아 설명글은 이쯤에서 마친다. 나중에 관련 문제를 풀고 나서 related에 문제 링크 추가 예정 (완료!).