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

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

 

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

2188번: 축사 배정

---

#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)