백준(C++) 11376번 열혈강호 2 풀이

C++로 구현한 11376번 열혈강호 2 구하기 문제 풀이입니다.

 

https://www.acmicpc.net/problem/11376

11376번: 열혈강호 2

---

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

using namespace std;

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

bool dfs(int x) {
	for(int i=0; i<a[x].size(); i++) {
		int t = a[x][i];
		if(c[t]) continue;
		c[t] = true;
		if(d[t] == 0 || dfs(d[t])) {
			d[t] = x;
			return true;
		}
	}
	return false;
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) {
		scanf("%d", &s);
		for(int j=1; j<=s; j++) {
			int t;
			scanf("%d", &t);
			a[i].push_back(t);
		}
	}
	int count = 0;
	for(int j=1; j<=2; j++) {
		for(int i=1; i<=n; i++) {
		fill(c, c+MAX, false);
		if(dfs(i)) count ++;
		}
	}
	printf("%d\n", count);
}

 

문제에서 직원의 수와 일의 개수 범위가 1,000까지이기 때문에 MAX의 값을 1,001로 지정해준다.

 

메인 코드에서 직원의 수와 일의 개수를 입력받고 첫번째 반복문을 통해 각 i번째 직원이 할 수 있는 일의 개수와

 

일의 번호를 입력받도록 한다. 입력받은 일의 번호를 i번째 직원과 매칭시켜 그래프를 형성한다.

 

세번째 반복문에서는 매번 매칭을 수행할 때마다 배열을 false 값으로 초기화해주고

 

dfs() 함수를 통해 새롭게 매칭이 이루어지면 count 값을 1 증가시켜준다.

 

문제에서 각 직원은 최대 두 개의 일을 할 수 있다는 점에 대해서 위 세번째 반복문을 2번 반복시켜주도록 한다.

 

이분매칭 알고리즘 수행에 해당하는 dfs() 함수에서는 연결된 모든 노드에 대해서 들어갈 수 있는지 시도하는데,

 

해당 일의 번호 값이 true값이라면 넘어가고 그렇지 않다면 true 값으로 지정해준다.

 

그리고 만약 해당 노드가 비어있거나 점유 노드에 더 들어갈 공간이 있는 경우에는 매칭시켜 준 뒤 true값을 반환한다.

 

 

  * 이분 매칭 알고리즘 수행 과정 및 정보는 아래의 글에서 확인하시면 됩니다.

https://unie2.tistory.com/47?category=873806

이분 매칭(Bipartite Matching)