이분 매칭 알고리즘이란?
이분 매칭 알고리즘은 선택하는 집단과 선택되는 집단이 있을 때, 두 집단 사이의 매칭 수가 최대가 되도록 하는 것이 목적인 알고리즘이다.
이분 매칭 알고리즘의 기본 원리
사람 A, B와 과일 X, Y, Z가 있는데, 한 사람당 하나의 과일만 먹을 수 있다고 가정하자.
사람 A는 모든 과일을 좋아해서 과일 X, Y, Z 모두를 선호하는 반면, 사람 B는 입맛이 까다로워서 과일 X만 선호한다.
초기 상태에서는 과일 X, Y, Z는 아무에게도 선택되지 않았다.
먼저, A가 선호하는 첫 번째 과일인 X를 매칭한다.
그 다음 B가 선호하는 첫 번째 과일인 X를 매칭하려고 하니 X는 A에 의해 이미 선택되어 있다.
그래서 B는 X를 선택한 A에게 이렇게 묻는다. "A님, 가능하다면 다른 과일을 선택해주실 수 있으신지요?"
A가 선호하는 과일은 X, Y, Z이므로, 현재 선택중인 X외에도 Y, Z과일을 선택할 수 있다. A는 B의 요구를 받아들이고 그 다음 과일인 Y를 선택한다.
B는 A의 양보 덕분에 과일 X를 먹을 수 있는 것이다.
결과적으로 A는 과일 X를, B는 과일 Y을 먹을 수 있다.
이런식으로 선택하려는 요소가 이미 매칭되어 있을 때, 그 요소를 선택중인 요소가 다른 요소를 선택할 수 있는지 결정하는 과정을 DFS 방식으로 반복하는 방법이 이분 매칭인 것이다.
이 11375번 문제가 가장 기초적인 이분 매칭 문제라고 볼 수 있다.
문제 해설
아래 그림은 11375번 문제의 입력 예시 케이스에 대한 결과다.
어떻게 이런 결과가 나왔는지 알아보자.
step 1 : A1은 B1와 매칭된다.
step 2 : A2는 B1을 선택중인 A1에게 다른 요소를 선택할 수 있는지 묻는다.
step 3 : A1은 B2를 선택할 수 있기 때문에 수락한다. A1은 B2와 매칭된다.
step 4 : A2는 B1와 매칭된다.
step 5 : A3는 B2를 선택중인 A1에게 다른 요소를 선택할 수 있는지 묻는다.
step 6 : A1은 B1을 선택중인 A2에게 다른 요소를 선택할 수 있는지 묻는다.
step 7 : A2는 B1외에는 선택지가 없으므로 거절한다. A1도 더 이상 선택지가 없으므로 A3의 요구를 거절한다.
step 8 : A3은 B3와 매칭된다.
step 9 : A4는 B3을 선택중인 A3에게 다른 요소를 선택할 수 있는지 묻는다.
step 10 : A3은 B2를 선택중인 A1에게 다른 요소를 선택할 수 있는지 묻지만, 앞서 A1, A2는 더 이상 선택지가 없음을 확인했다. A1은 A3의 요구를 거절한다.
step 11 : A4는 B4와 매칭된다.
step 12 : A5는 B1를 선택중인 A2에게 다른 요소를 선택할 수 있는지 묻지만, A2는 더 이상 선택지가 없으므로 거절한다.
step 13 : A5는 매칭에 실패한다.
소스 코드
#include <iostream>
#include <vector>
using namespace std;
bool v[1001]; // 요구가 무한히 반복되는 것을 방지
int room[1001];
vector<int> a[1001];
bool dfs(int x) {
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
if (v[y]) continue;
v[y] = true;
if (room[y] == 0 || dfs(room[y])) {
room[y] = x;
return true;
}
}
return false;
}
int main() {
int n, m, x, y;
int count = 0;
cin >> n >> m;
for (int i = 1; i < n + 1; i++) {
cin >> x;
for (int j = 0; j < x; j++) {
cin >> y;
a[i].push_back(y);
}
}
for (int i = 1; i < n + 1; i++) {
if (dfs(i)) count++;
fill(v, v + 1001, false);
}
cout << count << "\n";
}
추가 개념
만약 한 직원당 2개의 일을 할 수 있는 경우에는 dfs를 한번 더 수행하면 된다.
...
for (int i = 1; i < n + 1; i++) {
if (dfs(i)) count++;
fill(v, v + 1001, false);
if (dfs(i)) count++;
fill(v, v + 1001, false);
}
...
댓글