[백준문제풀이] 11375 열혈강호

 

풀이일시 : 2020-08-23

​

 

문제 :

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

​

 

입력:

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

ex)

5 5

2 1 2

1 1

2 2 3

3 3 4 5

1 1

​

 

출력:

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

ex)

4

​

 

풀이 :

첫째줄 입력이 2 1 2 라면 1번직원은 2가지의 일 할수있고 1번과 2번일을 할 수 있다는 것이다.

그 중에서 한 가지 일만 할 수 있고 일을 최대한 많이 하게끔 하는 경우를 구하는 것으로 이분매칭을 사용한다.

 

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

using namespace std;

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

bool dfs(int x) {
	for (int i = 0; i < a[x].size(); i++) {
		int t = a[x][i]; //인접노드 탐색 => t
		if (c[t])
			continue; //다음 for문
		c[t] = true; //방문체크
		if (d[t] == 0 || dfs(d[t])) {
			d[t] = x;
			return true; //한사람과 그 일이 매칭된것
		}
	}
	return false;
}

int main() {
	scanf_s("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf_s("%d", &s);
		for (int j = 0; j < s; j++) {
			int t;
			scanf_s("%d", &t);
			a[i].push_back(t);
		}
	}
	int count = 0;
	for (int i = 1; i <= n; i++) {
		fill(c, c + MAX, false); //방문체크를 위함. 매 dfs전에 초기화해준다.
		if (dfs(i))
			count++;
	}
	printf("%d", count);
	return 0;
}