[P4] 백준 2188번 축사 배정 C++ 이분 매칭

리뷰

 

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

이분 매칭의 기초적이 문제, 최적화를 하는 것에 신경을 써봤다.

 

 

전역 변수

• N : 소 관련 배열의 최대 크기를 정의할 상수 변수
• M : 축사 관련 배열의 최대 크기를 정의할 상수 변수
• n : 소의 개수를 저장할 변수
• m : 축사의 개수를 저장할 변수
• c : 소가 원하는 축사의 개수를 저장할 변수
• j : 소가 원하는 축사의 번호를 저장할 변수
• ans : 축사의 들어갈 수 있는 소의 개수를 저장할 변수
• edges : 각 소가 원하는 축사의 번호를 저장할 벡터 배열
• mat : 축사에 배정된 소의 번호를 저장할 배열
• v : 축사를 방문한 시간을 저장할 배열
• t : 방문 시간을 저장할 변수

 

함수

 

 

 

문제풀이

1. dfs

bool dfs(int node) {
	if (v[node] == t) return false;
	v[node] = t;
	for (int next : edges[node]) {
		//if (v[next] == t) continue;
		//v[next] = t;

		if (!mat[next]) {
			mat[next] = node;
			return true;
		}
	}

	for (int next : edges[node]) {
		//if (v[next] == t) continue;
		//v[next] = t;

		if (dfs(mat[next])) {
			mat[next] = node;
			return true;
		}
	}
	return false;
}

 

소가 축사를 찾아 최대한 많은 소를 축사에 넣는 방법을 찾기 위한 함수

 

트러블 슈팅

없음

 

 

참고 사항

• dfs 내부에서 mat이 빈 노드부터 탐색하고, 없다면 dfs를 돌리는 로직을 수행하니 더 빠른 것 같다.
• 사실 n, m값이 작아서 시간의 큰 차이는 없어 보인다.

 

정답 코드

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

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

bool dfs(int node) {
	if (v[node] == t) return false;
	v[node] = t;
	for (int next : edges[node]) {
		//if (v[next] == t) continue;
		//v[next] = t;

		if (!mat[next]) {
			mat[next] = node;
			return true;
		}
	}

	for (int next : edges[node]) {
		//if (v[next] == t) continue;
		//v[next] = t;

		if (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) {
		cin >> c;
		while (c--) {
			cin >> j;
			edges[i].push_back(j);
		}
	}

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