최대 이분 매칭(Maximum Bipartite Matching) 알고리즘 완벽 정리

이분 매칭(Bipartite Matching)이란?

이분 매칭은 그래프에서 간선들의 집합을 선택하되, 그 집합 안의 어떤 두 간선도 같은 정점(끝점)을 공유하지 않도록 하는 방식입니다. 여기서 최대 매칭(Maximum Matching)은 이러한 조건을 만족하면서 가장 많은 수의 간선을 선택하는 매칭을 의미합니다.

최대 매칭을 찾으면 더 이상 새로운 간선을 추가할 수 없습니다. 만약 최대 매칭이 된 그래프에 간선을 하나 추가하면, 두 간선이 같은 정점을 공유하게 되어 더 이상 유효한 매칭이 아니기 때문입니다. 한 가지 흥미로운 점은, 하나의 이분 그래프에는 서로 다른 최대 매칭이 둘 이상 존재할 수 있다는 것입니다.

대표적인 활용 예시로 '지원자와 직업' 문제가 있습니다. 여러 명의 지원자와 여러 개의 직업 자리가 있을 때, 각 지원자가 지원 가능한 직업이 정해져 있다면 최대 몇 명에게 직업을 배정할 수 있는지 구하는 문제가 바로 최대 이분 매칭 문제입니다.

입력과 출력

입력:
인접 행렬(adjacency matrix)
0 1 1 0 0 0
1 0 0 1 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1

출력:
Maximum number of applicants matching for job: 5

위 인접 행렬에서 행(row)은 지원자를, 열(column)은 직업을 나타냅니다. 값이 1이면 해당 지원자가 그 직업에 지원 가능함을 의미합니다.

알고리즘

bipartiteMatch(u, visited, assign)

입력: 시작 노드 u, 방문 여부를 추적하는 visited 리스트, 노드 간 배정 관계를 저장하는 assign 리스트

출력: 정점 u에 대한 매칭이 가능하면 true 반환

Begin
   for all vertex v, which are adjacent with u, do
      if v is not visited, then
         mark v as visited
         if v is not assigned, or bipartiteMatch(assign[v], visited, assign) is true, then
            assign[v] := u
            return true
   done
   return false
End

핵심 아이디어는 다음과 같습니다. 지원자 u가 원하는 직업 v가 이미 다른 지원자에게 배정되어 있더라도, 그 기존 지원자를 다른 직업으로 옮겨줄 수 있다면 u에게 v를 배정할 수 있습니다. 이것이 재귀 호출 bipartiteMatch(assign[v], visited, assign)가 수행하는 역할입니다.

maxMatch(graph)

입력: 주어진 그래프

출력: 최대 매칭 수

Begin
   initially no vertex is assigned
   count := 0
   for all applicant u in M, do
      make all node as unvisited
      if bipartiteMatch(u, visited, assign), then
         increase count by 1
   done
End

모든 지원자에 대해 순차적으로 매칭을 시도하고, 성공할 때마다 카운트를 증가시킵니다. 각 시도 전에 방문 배열을 초기화하여 경로 탐색이 올바르게 이루어지도록 합니다.

C++ 예제 코드

#include <iostream>
#define M 6
#define N 6
using namespace std;

bool bipartiteGraph[M][N] = {    // M명의 지원자와 N개의 직업으로 구성된 그래프
   {0, 1, 1, 0, 0, 0},
   {1, 0, 0, 1, 0, 0},
   {0, 0, 1, 0, 0, 0},
   {0, 0, 1, 1, 0, 0},
   {0, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 0, 1}
};

bool bipartiteMatch(int u, bool visited[], int assign[]) {
   for (int v = 0; v < N; v++) {    // 모든 직업(0 ~ N-1) 검사
      if (bipartiteGraph[u][v] && !visited[v]) {    // 직업 v를 방문하지 않았고 u가 지원 가능한 경우
         visited[v] = true;    // 직업 v를 방문 처리
         // v가 비어 있거나, 기존 배정자를 다른 직업으로 옮길 수 있는 경우
         if (assign[v] < 0 || bipartiteMatch(assign[v], visited, assign)) {
            assign[v] = u;    // 지원자 u에게 직업 v 배정
            return true;
         }
      }
   }
   return false;
}

int maxMatch() {
   int assign[N];    // 어떤 직업이 어느 지원자에게 배정되었는지 추적하는 배열
   for(int i = 0; i<N; i++)
      assign[i] = -1;    // 처음에는 모든 직업이 비어 있음
   int jobCount = 0;

   for (int u = 0; u < M; u++) {    // 모든 지원자에 대해 반복
      bool visited[N];
      for(int i = 0; i<N; i++)
         visited[i] = false;    // 처음에는 아무 직업도 방문하지 않음
      if (bipartiteMatch(u, visited, assign))    // u가 직업을 얻은 경우
         jobCount++;
   }
   return jobCount;
}

int main() {
   cout << "Maximum number of applicants matching for job: " << maxMatch();
}

실행 결과

Maximum number of applicants matching for job: 5

시간 복잡도

이 알고리즘은 각 지원자마다 DFS 방식으로 증가 경로(augmenting path)를 찾습니다. 지원자 수를 V, 간선 수를 E라고 할 때, 한 번의 매칭 시도에 최대 O(E)가 소요되므로 전체 시간 복잡도는 O(V × E)입니다.

마무리

최대 이분 매칭은 지원자-직업 배정, 학생-강의실 배정, 네트워크 플로우 문제 등 다양한 실무 상황에 응용될 수 있는 핵심 알고리즘입니다. 위 코드의 재귀적 증가 경로 탐색 로직을 잘 이해해 두면, 호프크로프트-카프(Hopcroft-Karp) 알고리즘 같은 더 빠른 개선 버전을 학습할 때 큰 도움이 됩니다.