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

 

풀이일시 : 2020-08-23

​

 

문제 :

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

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 단, N명 중에서 K명은 일을 최대 2개할 수 있다.

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

​

 

입력:

첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N)

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

ex)

5 5 1

3 1 2 3

3 1 2 3

1 5

1 5

1 5

​

 

출력:

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

ex)

4

​

 

풀이 :

이전의 문제들과 달라진 점은 일반적으로 직원은 한 가지의 일을 할수 있고, 두 가지의 일을 할 수 있는 직원이 존재하는데 그 직원의 수를 K로 주어준다는 점이다. 조건에 맞게 dfs를 두번 돌리면 될 것이다.

 

dbstndi6316.tistory.com/59

[기본문제풀이] bipartite matching

dbstndi6316.tistory.com/64

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

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

using namespace std;

int m, n, k, 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 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;
}

int main() {

	scanf_s("%d %d %d", &n, &m, &k);
    //입력
	for (int i = 1; i <= n; i++) {
		scanf_s("%d", &s);
		for (int j = 1; j <= s; j++) {
			int t;
			scanf("%d", &t);
			a[i].push_back(t);
		}
	}
    //나눠서 dfs 돌려준다. 일단 1회 전체로 돌려준다.
	int count = 0;
	for (int i = 1; i <= n; i++) {
		fill(c, c + MAX, false);
		if (dfs(i))
			count++;
	}
    //두번 수행할 수 있는 사람의 인원수를(k) 추가로 돌려준다.
	int extra = 0;
	for (int i = 1; i <= n && extra < k; i++) {
		fill(c, c + MAX, false);
		if (dfs(i))
			extra++;
	}
	printf("%d", count + extra);
	return 0;
}