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

 

풀이일시 : 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

2 1 2

2 1 2

2 4 5

​

 

출력:

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

ex)

4

​

 

풀이 :

열혈강호 문제와 같은것 같지만 분석해보면 직원이 할 수 있는 일의 개수가 다르다.

여기서는 두 가지의 일을 할 수 있다.

이를 통해 최대 몇 가지의 일을 수행할 수 있는지 구하는 프로그램을 작성해야한다. 역시 이분매칭을 이용한다.

한 직원이 두가지의 일을 할 수 있으므로 dfs를 두 번 수행해주어 두 번 매칭을 해줄것이다.

 

dbstndi6316.tistory.com/59

[기본문제풀이] bipartite matching

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

using namespace std;

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

bool dfs(int x) {
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i]; //한사람이 할 수 있는 일 중 하나를 택한다.
		if (c[y])
			continue;
		c[y] = true;
		if (d[y] == 0 || dfs(d[y])) { //자리가 비어있거나 더 들어갈공간이 있다면
			d[y] = x;
			return true;
		}
	}
	return false; //점유하지 못한다면 false. 일못한다.
}

int main() {
	scanf_s("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) { //사람 수만큼 반복하며 일의 갯수를 받는다.
		int k; 
		scanf_s("%d", &k); //한사람이 처리할수있는 일의 갯수
		for (int j = 1; j <= k; j++) {
			int y;
			scanf_s("%d", &y);
			a[i].push_back(y); //사람에 따라(i) 할수있는일(y) 짝지어준다.
		}
	}
	int count = 0;
	for (int k = 0; k < 2; k++) { // 두개를 처리할수있으므로 dfs를 두번 돌게하면된다
		for (int i = 1; i <= n; i++) {
			fill(c, c + MAX, false);
			if (dfs(i))
				count++;
		}
	}
	printf("%d", count);
	return 0;
}