Algorithm 공부 #26 - 이분 매칭(Binary Matching)

 

Algorithm 공부 #26 - 이분 매칭

 

✏️이분 매칭이란?

이분 그래프에서 주로 사용하는 알고리즘

이분 그래프는 두 개의 정점 그룹이 존재할 때 모든 간선의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프

이러한 이분 그래프에서 예를 들어, 한 그룹은 X그룹, 다른 한 그룹은 Y그룹이고 간선의 방향은 X->Y라고 할 때

모든 경로의 방향은 X->Y인 그래프의 최대 유량을 구하는 것

 

 

✏️예시

먼저 알파벳 그룹과 숫자 그룹이 있다고 가정을 하면

A에서 갈 수 있는 숫자는 1과 3

B에서 갈 수 있는 숫자는 1과 2

C에서 갈 수 있는 숫자는 5

D에서 갈 수 잇는 숫자는 3

E에서 갈 수 있는 숫자는 2

 

A부터 매칭을 시작하면 각 점에서는 한 개의 숫자만 갈 수 있으므로

A는 1과 연결(총 매칭 수1)

 

B는 1과 2로 갈 수 있지만 가장 먼저 1을 선택, 여기서 A에게 1을 써도 되냐고 물어봄

A는 1이외에도 3으로 갈 수 있으므로 B에게 1을 내주고 A는 3으로 연결

그렇게 되면 A는 3과 연결, B는 1과 연결(총 매칭 수2)

C는 갈 수 있는 곳이 5밖에 없으므로 5와 연결

현재까지 A는 3, B는 1, C는 5와 연결(총 매칭 수3)

D가 조금 복잡함. D는 갈 수 있는 곳이 3이므로 A에게 3으로 가도 되냐고 요청함 

A는 3말고 갈 수 있는 곳이 1이므로 1을 점유하고 있는 B에게 1로 가도 되냐고 요청

B는 1말고도 2로 갈 수 있으므로 B가 2로가고 A가1로 가고 D가 3으로 감

현재까지 A는 1, B는 2, C는 5, D는 3과 연결(총 매칭 수4)

E는 2와 연결을 해야함. E는 B에게 2를 써도 되냐고 요청함. 그러면 B는 A에게 1을 요청해야 되고,

A는 D에게 3을 요청해야 하지만, D가 갈 수 있는 곳은 3밖에 없으므로 요청은 무산됨

따라서 E는 갈 수 있는 곳이 없음

매칭 결과

A는 1  / B는 2 / C는 5 / D는 3/ E는 X

총 매칭 수 : 4

위의 그림은 "yjg-lab"의 블로그에서 캡쳐해왔습니다.

 

 

✏️알고리즘 구현하기

알고리즘 구현을 하기 전에 필요한 자료구조들이 있습니다.

가장 먼저 간선의 정보를 입력받을 vector<int>배열 

X그룹과 Y그룹이 있고 X->Y라고 할 때, Y로 오는 X그룹의 정점들의 정보를 저장할 node배열

그리고 Y그룹들의 정점을 사용할 수 있는지 확인할 visit배열

위 알고리즘은 dfs방식으로 구현할 것이기 때문에 dfs함수가 필요

 

✏️소스코드로 구현

#include<iostream>
#include<vector>
using namespace std;
#define MAX 201
int N, M;

vector<int>graph[MAX]; // 간선의 정보를 입력받음
int node[MAX]; // Y그룹으로 오는 X그룹의 정보를 저장
bool visit[MAX]; // Y그룹의 정점의 사용 가능 여부 체크
bool dfs(int cow); // 처리할 수 있으면 TRUE를 아니라면 FALSE를 RETURN

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;

	for (int i = 1; i <= N; i++) { // 그래프 구현
		int number;
		cin >> number;
		while (number--) {
			int shed;
			cin >> shed;
			graph[i].push_back(shed);
		}
	}

	int count = 0;
	for (int i = 1; i <= N; i++) { // X그룹의 각 정점들에 대해서 DFS로 탐색을 하면서 매칭을 시작
		fill(visit, visit + MAX, false);
		if (dfs(i)) // 매칭이 가능
			count++;
	}

	cout << count;
}

bool dfs(int cow)
{
	for (int i = 0; i < graph[cow].size(); i++) { // X그룹의 각 정점들이 갈 수 있는 곳으로 탐색
		int shed = graph[cow][i]; // X->Y가 가능한 Y의 정점들
		if (visit[shed]) // 이미 방문할 수 없는 곳들
			continue;
		visit[shed] = true;
		if (node[shed] == 0 || dfs(node[shed])) { // 아직 X그룹의 정점들이 도달하지 못했거나, 요청을 해서 바꿀 수 있는 것들
			node[shed] = cow; // 최신 정점으로 갱신
			return true;
		}
	}
	return false;
}

 

 

✏️문제로 이해하기

https://pooreumjung.tistory.com/339

[C/C++] 백준 열혈강호 문제 모음 / 백준 11375번, 백준 11376번

https://pooreumjung.tistory.com/340

[C/C++] 백준 2188번 - 축사 배정