[P4] 백준 11375번 열혈강호 C++ 이분 매칭

리뷰

 

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

이분 매칭의 기본이 되는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의하기 위한 상수 변수
• n : 직원의 수를 저장할 변수
• m : 일의 개수를 저장할 변수
• mat : 일을 담당하는 직원의 번호를 저장할 배열
• v : 일이 탐색된 시간을 저장할 배열
• t : 현재 탐색 중인 시간을 저장할 변수
• edges : 직원이 담당할 수 있는 일의 번호를 저장할 벡터 배열

 

함수

1. dfs

bool dfs(int node) {
	for (int next : edges[node]) {
		if (v[next] == t) continue;
		v[next] = t;
		if (!mat[next] || dfs(mat[next])) {
			mat[next] = node;
			return true;
		}
	}
	return false;
}

 

현재 직원이 담당할 수 있는 일을 탐색하기 위한 함수

 

문제풀이

• n, m에 값을 입력 받는다.
• 1~n번 직원이 수행할 수 있는 일의 번호를 edges배열의 벡터에 추가해 준다.
• 변수 ans를 0으로 초기화 해준다.
• 1~n번 직원을 순회하며 t값을 1만큼 증가시켜 준다.
• dfs함수에 i를 매개변수로 전달하여 리턴값이 true라면 ans를 증가시켜 준다.
• ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• v를 bool타입으로 지정 후 매번 memset을 해주는 것 보다 int타입 및 t를 통해 접근 시간을 통해 관리해 주니 시간 복잡도가 소폭 감소하였다.

 

정답 코드

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int N = 1001;
int n, m;
int mat[N];
int v[N];
int t;
vector<int> edges[N];

bool dfs(int node) {
	for (int next : edges[node]) {
		if (v[next] == t) continue;
		v[next] = t;
		if (!mat[next] || dfs(mat[next])) {
			mat[next] = node;
			return true;
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		int j; cin >> j;
		while (j--) {
			int b; cin >> b;
			edges[i].push_back(b);
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		t++;
		if (dfs(i)) ans++;
	}
	cout << ans << "\n";
}