백준11375 - 열혈강호

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

11375번: 열혈강호

이분 매칭을 이용하여 풀었다. 나동빈님 블로그에서 참고하였다. 이분 매칭은 a 집단에서 b 집단을 일대일로 각 원소를 매칭하는데 최대로 매칭해 줄 수 있는 방법을 찾는 방법이다. dfs를 이용하여 구현한다.  구현 원리는 임의의 점이 도착하려는 자리에 어떤 원소가 이미 도착했다면 다른 곳으로 옮겨갈 수 있는지 판별하고 옮겨갈 수 있는 점이 있다면 그 점으로 이동시키고 현재 들어가려는 원소를 넣어준다.

 

#include <iostream>
#include <vector>
#define MAX 1001
using namespace std;

vector<int> a[MAX]; //각각의 노드 v[x][y]면 x에서 y를 선택한다는 뜻
int d[MAX]; //각 출발점에서 도착점을 담을 공간
bool c[MAX]; //특정한 정점을 처리했는지 확인하는 변수
int N, M;
int num;
int work;
int cnt = 0;

bool dfs(int x) {
	for (int i = 0; i < a[x].size(); i++) {
		int t = a[x][i];

		if (c[t]) { //이번 순서에서 이미 t점에 방문 한 적이 있으면
			continue; //무시
		}

		c[t] = true; //t점을 방문처리

		if (d[t] == 0 || dfs(d[t])) { //아직 t점으로 도착한 점이 없거나 다른 이미 점유하고 있는 점에서 다른 곳으로 이동할 곳이 있으면
			d[t] = x; //현재 점 x를 t에 도달할 수 있다고 지정
			return true; //매칭 성공
		}
	}
	return false; //매칭 실패
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> num;
		for (int j = 0; j < num; j++) {
			cin >> work;
			a[i].push_back(work);
		}
	}

	for (int i = 1; i <= N; i++) {
		fill(c, c + MAX, false);

		if (dfs(i)) { //매칭이 성공되면
			cnt++; //성공된 매칭의 갯수 증가
		}
	}

	cout << cnt;
}