[백준] 11377번: 열혈강호 3

---

문제링크 : [백준] 11377번: 열혈강호 3

11377번: 열혈강호 3

1. 문제

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

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

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

---

2. 입출력

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

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

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

---

3. 문제 풀이 및 코드

직원 , 해야할 일 이 두가지 집단간의 최대 매칭을 찾아야하는 문제였습니다. 직원 집단과 해야할 일 집단은 그 각각의 집단 요소 끼리는 간선이 없고 직원 집단과 일 집단 사이에만 간선이 존재하므로 이분 그래프로 여길 수 있습니다. 이분 그래프에서 간선의 용량이 모두 1인 최대 매칭을 구하는 알고리즘인 이분 매칭을 DFS를 이용하여 구현했습니다. 

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000 + 1;
int workers[MAX],tasks[MAX],N,M,K;
bool visited[MAX];
vector<vector<int>> canDo;

bool dfs(int a){
	if(visited[a]) return false;
	visited[a] = true;
	for(int i=0;i<(int)canDo[a].size();i++) {// worker a가 할 수 있는 일 탐색.
		int b = canDo[a][i];
		if(!tasks[b]||dfs(tasks[b])) {
			tasks[b] = a;
			workers[a] = b;
			return true;
		}
	}
	return false;
}

int biMatching(){						
	int ans = 0;
	for(int i=1;i<=N;i++){	// 최대 매칭 한 번 진행.
		memset(visited,0,sizeof(visited));
		if(dfs(i)) ans++;
	}
    
	
	for(int i=1;i<=N;i++){	// 매칭이 끝나고 일을 2번 할 수있는 K명의 직원과 일을 매칭.
		memset(visited,0,sizeof(visited));
		if(dfs(i)){ 
			ans++; 
			K--;
			if(!K) break;
		}
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>M>>K;
	canDo.resize(N+1);
	for(int i=1;i<=N;i++) {
		int cnt;
		cin>>cnt;
		while(cnt--){
			int taskNum;
			cin>>taskNum;
			canDo[i].push_back(taskNum); // i번째 직원이 할 수 있는일 저장.
		}
	}
	cout<<biMatching()<<"\n";	

	return 0;
}

---

4. 마무리

이분 매칭 알고리즘에 대해서는 추후 포스팅으로 남기겠습니다! 부족한 부분 지적 언제든 댓글로 부탁드립니다^^.