이분 매칭 알고리즘
이분 매칭 알고리즘은 그래프 이론과 연관된 문제를 푸는 데 사용되는 알고리즘 중 하나로, 주로 "양쪽 그룹 사이의 최적의 매칭"을 찾는 데 활용됩니다. 예를 들어, 여러 학생과 각 학생마다 선호하는 동반자가 주어졌을 때, 이분 매칭 알고리즘은 모든 학생들이 서로 다른 동반자와 짝지어지며 최대한 많은 학생들이 선호하는 동반자와 짝지어지는 최적의 방법을 찾아냅니다.
동작 원리
1. 이분 그래프 생성: 먼저, 매칭을 하려는 두 그룹을 각각 왼쪽(L)과 오른쪽(R)으로 나누어 이분 그래프를 생성합니다. 이분 그래프는 왼쪽 그룹의 각 노드와 오른쪽 그룹의 각 노드 사이에 연결된 간선을 나타냅니다.
2.
초기 매칭 설정: 초기에는 모든 노드는 매칭되지 않은 상태입니다. 이후 알고리즘을 통해 매칭을 확장해나갑니다.
3.
증가 경로 찾기: 매칭이 확장되려면, "증가 경로"를 찾아야 합니다. 증가 경로란 매칭되지 않은 왼쪽 그룹 노드부터 시작하여 교대로 매칭되지 않은 오른쪽 그룹 노드로 이어지는 경로를 말합니다. 이 증가 경로가 존재한다면 매칭을 더 확장할 수 있습니다.
4.
매칭 확장: 증가 경로를 찾았다면, 해당 경로에 속한 매칭을 반전시킴으로써 매칭을 확장합니다. 이는 이미 매칭된 노드와 새로운 노드를 교대시키는 것을 의미합니다.
5.
최대 매칭 찾기: 증가 경로를 더 이상 찾을 수 없을 때까지 위의 단계를 반복합니다. 이 과정을 통해 최대한 많은 노드들이 서로 매칭되며, 더 이상 증가 경로를 찾을 수 없는 상태에서 알고리즘은 종료됩니다.
https://www.acmicpc.net/problem/2188
2188번: 축사 배정
농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해
www.acmicpc.net
예시로 2188번을 풀어보았다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <bits/stdc++.h>
#define MAX 987654321
#define MIN -987654321
using namespace std;
typedef long long int ll;
typedef pair<int, int> pi;
typedef pair<int, pair<int, int>>pi2;
int T, N, M;
int num;
int visited[205];
int d[205];
vector<vector<int>>v;
bool solve(int x)
{
for (auto num : v[x])
{
if (visited[num])continue;
visited[num] = 1;
if (!d[num] || solve(d[num]))
{
d[num]=x;
return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
int i;
v.resize(201);
for (i = 1; i <=N; i++)
{
cin >> T;
while (T--)
{
cin >> num;
v[i].push_back(num);
}
}
int res = 0;
for (i = 1; i <= N; i++)
{
fill(visited, visited + 201, 0);
if (solve(i))
{
res++;
}
}
cout << res;
}
|
cs |