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

리뷰

 

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

작업자가 최대 2개까지의 작업을 수행할 수 있는 문제

 

 

전역 변수

• N : 작업자 관련 배열의 최대 크기를 정의할 상수 변수
• M : 작업 관련 배열의 최대 크기를 정의할 상수 변수
• n : 작업자의 수를 저장할 변수
• m : 작업의 개수를 저장할 변수
• c : 작업자 당 작업의 개수를 저장할 변수
• j : 작업의 번호를 저장할 변수
• ans : 수행할 수 있는 작업의 개수를 저장할 변수
• edges : 작업자가 수행할 수 있는 작업의 번호를 저장할 벡터 배열
• match : 작업을 맡은 작업자 번호를 저장할 배열
• v : 마지막으로 작업을 순회한 시간을 저장할 배열
• t : 순회 시간을 저장할 변수

 

함수

1. dfs

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

 

작업자가 수행할 수 있는 작업을 순회하며 갱신하고, 작업을 맡을 수 있는지 여부를 판단하는 함수

 

문제풀이

• n, m값을 입력 받고, n명의 작업자가 맡을 수 있는 작업의 번호를 edges배열에 저장한다.
• 1~n번의 작업자를 순회하며 dfs함수를 통해 작업을 맡을 수 있는지 여부를 탐색한다.
• 매 탐색 이전에 t를 증가시켜 작업의 순회 시간을 갱신시켜 준다.
• 만약 dfs함수에 i를 전달한 리턴값이 true라면 ans를 증가시켜 준다.
• ans가 m과 동일할 경우 모든 작업을 완료한 상태이므로 break처리해 준다.
• ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

• dfs함수 내부에서 재귀를 진행할 때 매개변수로 next를 전달해 주어 Fail을 받았다.
• 작업과 작업 사이에 t를 증가시켜 주지 않아 Fail을 받았다.
• 매개변수를 next가 아닌 match[next]로 변경해 주니 AC를 받았다.

 

참고 사항

• 한명의 작업자가 두번의 dfs를 통해 작업을 순회하지만 t를 통해 둘은 다른 작업자임을 명시해 주어야 한다.
• ans가 m과 동일할 경우 더 이상 탐색할 필요가 없으므로 break처리해 준다.
• 더 나아가 ans가 n * 2에 도달할 경우에도 break처리해 줘도 될 것 같다.

 

정답 코드

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

const int N = 1001;
const int M = 1001;
int n, m, c, j, ans;
vector<int> edges[N];
int match[M];
int v[M];
int t;

bool dfs(int node) {
	for (int next : edges[node]) {
		if (v[next] == t) continue;
		v[next] = t;
		if (!match[next] || dfs(match[next])) {
			match[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) {
		cin >> c;
		while (c--) {
			cin >> j;
			edges[i].push_back(j);
		}
	}

	for (int i = 1; i <= n; ++i) {
		t++;
		if (dfs(i)) ans++;
		t++;
		if (dfs(i)) ans++;
		if (ans == m) break;
	}
	cout << ans;
}