현실 세계의 수많은 비즈니스 문제는 결국 '자원의 효율적인 배분'으로 귀결됩니다. "5명의 직원이 있고 5개의 서로 다른 업무가 있을 때, 각 직원의 희망 업무를 반영하여 최대한 많은 사람에게 업무를 배정하려면 어떻게 해야 할까?", "비행기 좌석을 고객들의 선호도에 맞춰 가장 많이 팔려면 어떻게 매칭해야 할까?" 이러한 일대일 대응의 배정(Assignment) 문제를 수학적이고 체계적으로 풀어내는 알고리즘이 바로 '이분 매칭(Bipartite Matching)'입니다. 유체 역학에서 파생된 복잡한 네트워크 플로우(Network Flow) 이론의 특수한 형태이지만, 코딩 테스트에서는 아주 간결한 DFS(깊이 우선 탐색) 로직만으로 O(V*E)의 빠른 속도에 뚝딱 해결해 낼 수 있는 마법 같은 알고리즘의 원리를 소개합니다.
1. 이분 그래프(Bipartite Graph)의 이해
이분 매칭을 수행하기 위한 절대적인 전제 조건은 시스템 구조가 '이분 그래프' 형태를 띠어야 한다는 것입니다.
이분 그래프란, 그래프의 모든 정점(Node)을 완벽하게 두 개의 분리된 집합(예: 사람 집합 A, 업무 집합 B)으로 나눌 수 있는 구조를 말합니다. 가장 중요한 규칙은 "같은 집합에 속한 노드들끼리는 절대 선(간선)이 연결되어 있지 않으며, 오직 반대편 집합의 노드와만 연결 선을 가질 수 있다"는 점입니다. 이분 매칭은 이 두 집합 사이의 연결선(선호도)들을 활용하여, 선이 겹치지 않게(1인당 1업무) 가장 많이 연결하는 '최대 매칭(Maximum Matching)' 개수를 찾는 알고리즘입니다.
2. 이분 매칭의 핵심 아이디어: "양보와 밀어내기"
이 알고리즘의 천재성은 이미 자리를 차지한 사람에게 "혹시 다른 자리로 비켜줄 수 있니?"라고 물어보며 연쇄적인 자리 이동(Augmenting Path)을 유도하는 데 있습니다. DFS 탐색을 통해 직관적으로 시뮬레이션해 봅니다.
2-1. DFS 매칭 시뮬레이션의 전개
사람 A, B, C가 있고 업무 1, 2, 3이 있습니다.
(A는 1번, 2번 업무를 원함 / B는 1번을 원함 / C는 2번을 원함)
- 첫 번째 사람 A의 매칭: A가 자신이 원하는 첫 번째 업무인 '1번 업무'를 살펴봅니다. 비어있으므로 A가 1번 업무를 차지합니다. (현재 매칭: A-1)
- 두 번째 사람 B의 매칭: B는 오직 '1번 업무'만 원합니다. 그런데 1번 업무는 이미 A가 차지하고 있습니다. 여기서 매칭을 포기하는 것이 아니라, 1번 업무를 선점한 A에게 "혹시 네가 원하는 다른 빈 업무가 있는지 다시 알아봐 줄래?"라고 요청(재귀 DFS)합니다.
- 연쇄적인 양보 (Bumping): 양보 요청을 받은 A는 자신이 원했던 두 번째 리스트인 '2번 업무'를 쳐다봅니다. 다행히 2번 업무가 비어있습니다! A는 흔쾌히 1번을 B에게 넘겨주고 자신은 2번 업무로 이동합니다. (현재 매칭: B-1, A-2)
- 세 번째 사람 C의 매칭: C는 '2번 업무'를 원합니다. 2번은 A가 차지하고 있습니다. C는 A에게 비켜달라고 요청합니다. A는 1번 업무로 다시 옮겨갈 수 있는지 봅니다(1번은 B가 차지 중). A는 또다시 B에게 비켜달라고 요청합니다. 하지만 B는 1번 외에는 할 수 있는 업무가 없으므로 양보를 거절합니다. 연쇄 양보가 실패하여, A는 그대로 2번을 사수하고 C는 최종적으로 매칭에 실패합니다.
이렇게 모든 사람(노드)에 대해 DFS를 단 한 번씩만 수행하여 연쇄 양보를 시도하면, 가장 많은 사람이 업무를 배정받는 최적의 최대 매칭 수를 100% 완벽하게 구해낼 수 있습니다.
3. 네트워크 플로우와의 관계 (코드의 단순함)
원래 최대 매칭을 구하는 정석적인 방법은 포드-풀커슨(Ford-Fulkerson)이나 에드몬드-카프(Edmonds-Karp) 같은 무거운 네트워크 플로우(최대 유량) 알고리즘을 사용해 파이프에 물을 흘려보내는 것입니다. 이분 그래프 구조에서 모든 파이프의 최대 용량(Capacity)을 1로 제한하면 그것이 곧 이분 매칭이 됩니다.
하지만 이분 그래프라는 특수한 상황에서는 복잡한 큐(Queue)나 유량 계산 행렬을 짤 필요가 전혀 없습니다. 위에서 설명한 방문 기록 배열(Visited)과 누가 어느 자리를 차지하고 있는지 기록하는 배열(Occupied) 단 두 개와, 아주 짧은 10여 줄의 재귀 DFS 함수 하나만으로 네트워크 플로우의 기능을 100% 동일하게 시뮬레이션할 수 있습니다. 그래서 이분 매칭은 네트워크 플로우 계열 문제 중에서도 코딩 테스트 현장에서 가성비가 가장 압도적으로 좋은 꿀 알고리즘으로 꼽힙니다.
1. 이분 매칭(Bipartite Matching)은 사람과 업무처럼 완벽히 두 그룹으로 분리된 노드들 사이에서, 가장 많은 수의 1:1 짝(Matching)을 지어주는 알고리즘입니다.
2. 복잡한 유량 알고리즘 대신, 이미 매칭된 상대에게 "다른 빈 곳으로 양보할 수 있는지 연쇄적으로 묻는 DFS (Augmenting Path)" 로직을 통해 극도로 짧고 간결하게 구현합니다.
3. 축사 배정 문제, 노트북 배부 문제 등 자원 배분 상황에서 사용되며, O(V*E)의 빠른 시간 복잡도로 실무 스케줄링 시스템에 강력하게 응용됩니다.