백준(C언어) 풀이/이분 매칭

백준(C++) 2188번 축사 배정 풀이

개발윗미 2021. 8. 3. 14:41

C++로 구현한 2188번 축사 배정 구하기 문제 풀이입니다.

 

https://www.acmicpc.net/problem/2188

 

2188번: 축사 배정

농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해

www.acmicpc.net


#include <iostream>
#include <vector>
#define MAX 201

using namespace std;

vector<int> a[MAX];
int d[MAX];
bool c[MAX];
int n, m, s;

bool dfs(int x) {
	for(int i=0; i<a[x].size(); i++) {
		int t = a[x][i];
		if(c[t]) continue;
		c[t] = true;
		if(d[t] == 0 || dfs(d[t])) {
			d[t] = x;
			return true;
		}
	}
	return false;
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) {
		scanf("%d", &s);
		for(int j=1; j<=s; j++) {
			int t;
			scanf("%d", &t);
			a[i].push_back(t);
		}
	}
	int count = 0;
	for(int i=1; i<=n; i++) {
		fill(c, c+MAX, false);
		if(dfs(i)) count ++;
	}
	printf("%d\n", count);
}

 

문제에서 소의 수와 축사의 수 범위가 200까지이기 때문에 MAX의 값을 201로 지정해준다.

 

메인 코드에서 소의 수와 축사의 수를 입력받고 첫번째 반복문을 통해 각 i번째 소가 들어가기 원하는 축사의 수와

 

축사 번호를 입력받도록 한다. 입력받은 축사 번호를 i번째 소와 매칭시켜 그래프를 형성한다.

 

세번째 반복문에서는 매번 매칭을 수행할 때마다 배열을 false 값으로 초기화해주고

 

새롭게 매칭이 이루어지면 count 값을 1 증가시켜준다.

 

이분매칭 알고리즘 수행에 해당하는 dfs() 함수에서는 연결된 모든 노드에 대해서 들어갈 수 있는지 시도하는데,

 

해당 축사 번호 값이 true값이라면 넘어가고 그렇지 않다면 true 값으로 지정해준다.

 

그리고 만약 해당 노드가 비어있거나 점유 노드에 더 들어갈 공간이 있는 경우에는 매칭시켜 준 뒤 true값을 반환한다.

 

 

  * 이분 매칭 알고리즘 수행 과정 및 정보는 아래의 글에서 확인하시면 됩니다.

https://unie2.tistory.com/47?category=873806 

 

이분 매칭(Bipartite Matching)

이분 매칭은 집단이 존재할 때 A 집단이 B 집단을 선택하는 방법이다. 아래와 같이 숫자 집단과 알파벳 집단이 있다고 가정하고, 1번은 알파벳 A, B, C 를 선택하고 2번은 알파벳 A를, 3번은 알파벳 C

unie2.tistory.com