[백준문제풀이] 2188 축사배정

 

풀이일시 : 2020-08-23

​

 

문제 :

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

첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.

농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다.

 

 

입력:

첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)

둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.

ex)

5 5

2 2 5

3 2 3 4

2 1 5

3 1 2 5

1 2

​

 

출력:

첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.

ex)

4

​

 

풀이 :

DFS, 이분매칭(bipartite_matching) 개념이용

DFS를 이용하여 계속해서 매칭이 가능한 경우를 찾아내어 조건이 맞을경우 매칭시킨다.

 

dbstndi6316.tistory.com/64

[기본문제풀이] DFS 깊이우선탐색

 

dbstndi6316.tistory.com/59

[기본문제풀이] bipartite matching

#include <iostream>
#include <vector>
#define MAX 201 //소의 수와 축사의 수는 최대 200개

using namespace std;

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

bool dfs(int x) { //깊이우선탐색
	for (int i = 0; i < a[x].size(); i++) { //연결된 노드에 대하여 탐색한다.
		int t = a[x][i];
		if (c[t]) //이미 true라면 볼필요없이 다음 연결노드로 간다.
			continue;
		c[t] = true; //방문처리해준다.
		//비어있거나 점유노드에 더 들어갈 공간이 있는 경우
		if (d[t] == 0 || dfs(d[t])) { //재귀. 즉 dfs(d[t])로 다른곳에 공간이있는지 물어보는것
			d[t] = x; //t는 x를 차지함
			return true; //매칭 성공시 true
		}
	}
	return false; //매칭 실패시
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) { //축사의 수만큼 반복한다.
		cin >> s;
		for (int j = 1; j <= s; j++) { //소가 들어갈 수 있는 축사의 수 만큼 입력을 받아야된다.
			int t;
			cin >> t;
			a[i].push_back(t); //그 축사의 번호에 t를 연결해준다
		}
	}
	int count = 0;
	for (int i = 1; i <= n; i++) { //소의 수만큼 dfs 실행할것이다.
		fill(c, c + MAX, false); //dfs 전에 항상 c를 초기화시켜준다. d만 살려둘것
		if (dfs(i)) //1부터 축사의 수만큼 dfs를 실행한게 1을 반환하면 (소가 축사에 들어가면)
			count++; //count를 증가시킨다.
	}
	printf("%d\n", count);
	return 0;
}