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

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

 

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

11375번: 열혈강호

---

#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 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 값으로 초기화해주고

 

새롭게 매칭이 이루어지면 count 값을 1 증가시켜준다.

 

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

 

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

 

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

 

 

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

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

이분 매칭(Bipartite Matching)