[P4] 백준 4966번 Cards C++ 유클리드 호제법, 이분 매칭

리뷰

 

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

최대 공약수가 2이상인 카드끼리 최대한 많은 쌍을 만드는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 저장할 상수 변수
• arr : 파란색 카드 묶음의 숫자를 저장할 배열
• edges : 파란색 카드에서 빨간색 카드를 선택할 수 있는 간선을 저장할 정수형 벡터 배열
• n : 파란색 카드의 개수를 저장할 변수
• m : 빨간색 카드의 개수를 저장할 변수
• t : 방문 시각을 저장할 변수
• v : 빨간색 카드의 마지막 방문 시각을 저장할 배열
• match : 빨간색 카드에 매칭된 파란색 카드의 번호를 저장할 배열

 

함수

1. get_gcd

int get_gcd(int a, int b) {
	while (b) {
		int t = a % b;
		a = b;
		b = t;
	}
	return a;
}

 

두 수의 최대공약수를 구하기 위한 함수

 

2. dfs

bool dfs(int cn) {
	for (int nn : edges[cn]) {
		if (!match[nn]) {
			match[nn] = cn;
			return true;
		}
	}

	for (int nn : edges[cn]) {
		if (v[nn] == t) continue;
		v[nn] = t;

		if (dfs(match[nn])) {
			match[nn] = cn;
			return true;
		}
	}

	return false;
}

 

이분 매칭을 통해 현재 파란색 카드가 연결될 수 있는 빨간색 카드가 있는지 여부를 판별하기 위한 함수

 

 

문제풀이

1. 무한 루프를 수행하고, 매 루프마다 n, m값을 입력 받아준다.
2. 기저 조건으로 n, m이 모두 0일경우 break처리한다.
3. n개의 파란색 카드에 적힌 수를 입력 받아 arr배열을 초기화 하고, edges를 clear처리한다.
4. m개의 빨간색 카드에 적힌 수를 입력 받아 변수 a에 저장한다.
5. 파란색 카드를 순회하며 변수 g에 get_gcd함수를 통해 두 수 사이의 최대 공약수를 저장한다.
6. 만약 g가 1이면 continue처리하고, 아니라면 파란색 카드의 edges에 빨간색 카드의 번호를 추가한다.
7. 변수 ans를 0으로 초기화하고, memset함수를 통해 이전 테스트케이스에서 사용했던 match배열을 0으로 초기화한다.
8. 파란색 카드를 순회하며, 매 루프마다 t를 증가시킨다.
9. dfs함수에 현재 파란색 카드 번호를 매개변수로 전달하여 호출한다.
10. dfs함수 내부에선 자신의 인접 리스트를 순회하며 match의 값이 아직 0인 빨간색 카드가 있다면 추가하고 true를 리턴한다, 아니라면 재귀를 통해 그러한 케이스가 있을때까지 순회하고, 교체가 가능하면 변경 후 true를 리턴한다.
11. 위 두 조건에 해당하는 케이스가 존재하지 않는다면 false를 리턴한다.
12. dfs함수의 최종 결과값이 true인 경우 ans를 증가시킨다.
13. 모든 탐색을 마친 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. C++17이상의 numberic헤더를 사용해 gcd함수를 사용할 수 있는 것으로 알았는데 BOJ제출 시 에러가 발생했다.
2. 따라서 유클리드 호제법을 사용한 get_gcd커스텀 함수를 사용해주었다.

 

정답 코드

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

const int N = 501;
int arr[N];
vector<int> edges[N];
int n, m, t;
int v[N];
int match[N];

int get_gcd(int a, int b) {
	while (b) {
		int t = a % b;
		a = b;
		b = t;
	}
	return a;
}

bool dfs(int cn) {
	for (int nn : edges[cn]) {
		if (!match[nn]) {
			match[nn] = cn;
			return true;
		}
	}

	for (int nn : edges[cn]) {
		if (v[nn] == t) continue;
		v[nn] = t;

		if (dfs(match[nn])) {
			match[nn] = cn;
			return true;
		}
	}

	return false;
}

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

	while (1) {
		cin >> n >> m;
		if (!n && !m) break;

		for (int i = 1; i <= n; ++i) {
			cin >> arr[i];
			edges[i].clear();
		}

		for (int i = 1; i <= m; ++i) {
			int a; cin >> a;

			for (int j = 1; j <= n; ++j) {
				int g = get_gcd(arr[j], a);
				if (g == 1) continue;

				edges[j].push_back(i);
			}
		}

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