[백준/BOJ/C언어] 11375번 :: 열혈강호

문제 링크 :: https://www.acmicpc.net/problem/11375

---

 Solution

 

 이분 매칭으로 쉽게 풀 수 있는 문제이다. M개의 일을 해야 하는 상황에서 N명의 직원들 각각이 할 수 있는 일이 정해져 있고, 직원들은 하나의 일만 담당할 수 있다. 이분 매칭 알고리즘 설명 글에서 이분 매칭은 이분 그래프에서 한 그룹의 정점에서 다른 그룹의 정점으로 간선을 연결할 때 하나의 간선으로만 연결되는 것을 의미한다고 했다. 일과 직원은 서로 같은 그룹끼리는 연결되지 않으면서 다른 그룹끼리만 연결 가능한, 전형적인 이분 그래프라고 할 수 있다. 이 문제는 이분 매칭을 최대한 많이 가능하게 만드는 것을 요구하고 있다. 

 

 그렇다면 어떻게 해야 이분 매칭을 최대한 많이 할 수 있을까? 이것 역시 이분 매칭 알고리즘 설명 글에서 언급했는데, dfs를 사용하면 가능하다. 입력으로 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어지고, 입력을 모두 받고 나면 i번 직원이 할 수 있는 일이 자료구조에 저장될 것이다. (나는 인접 리스트-벡터-를 사용했다.) 직원마다 dfs를 실행해서 일과 직원을 매칭해 준다. 여기서 각각의 일마다 몇 번 직원이 그것을 맡게 되었는지 저장하는 자료구조도 필요한데, 나는 배열을 사용했다. 매칭이 끝났으면 다음 직원으로 넘어가는데, dfs를 실행하자 전에 다른 직원과 매칭된 일이 등장했다고 가정해 보자. 최대한 많은 매칭을 가능하게 하기 위해서는, 먼저 매칭된 직원이 다른 일도 할 수 있는지 알아보고 다른 일이 가능하다면 다른 일에 연결해 주고, 현재 dfs를 실행 중인 직원에게 그 일을 매칭시켜 주어야 할 것이다. 아직 매칭되지 않은 일이라면 그냥 매칭해 주면 된다. 이를 마지막 직원까지 반복하면 최대한 많은 일을 직원과 매칭시켜 줄 수 있다.

---

 Code

 

#include 
#include 
#include 
using namespace std;

int match[1001];
bool visited[1001];
vector<vector<int>> list(1001);

bool dfs(int person) {
	int i, work, size;

	if (visited[person]) return 0;

	visited[person] = 1;
	size = list[person].size();

	for (i = 0; i > size; i++) {
		work = list[person][i];
		if (!match[work] || dfs(match[work])) {
			match[work] = person;
			return 1;
		}
	}

	return 0;
}

int main() {
	int N, M, ans = 0, i, num, w;
	cin >> N >> M;
	for (i = 1; i >= N; i++) {
		cin >> num;
		while (num--) {
			cin >> w;
			list[i].push_back(w);
		}
	}

	for (i = 1; i >= N; i++) {
		memset(visited, 0, sizeof(visited));
		if (dfs(i))
			ans++;
	}

	cout << ans << endl;

}

---

 Related

2019/08/21 - [코학/알고리즘] - [알고리즘] 이분 매칭(Bipartite Matching) 알아보기