[P4] 백준 18138번 리유나는 세일러복을 좋아해 C++ 이분 매칭

리뷰

 

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

조건에 맞는 연결 리스트를 작성하여 티셔츠와 카라를 조합할 수 있는 최대 가짓수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• T : 티셔츠의 넓이를 저장하기 위한 배열
• K : 카라의 넓이를 저장하기 위한 배열
• n : 티셔츠의 개수를 저장할 변수
• m : 카라의 개수를 저장할 변수
• M : 카라에 매칭된 티셔츠의 번호를 저장할 배열
• v : 마지막으로 방문한 시간을 저장할 배열
• t : 방문 시간을 저장할 변수

 

함수

1. dfs

bool dfs(int sn) {
	if (v[sn] == t) return false;
	v[sn] = t;

	for (int nn : edges[sn]) {
		if (!M[nn]) {
			M[nn] = sn;
			return true;
		}
	}

	for (int nn : edges[sn]) {
		if (dfs(M[nn])) {
			M[nn] = sn;
			return true;
		}
	}

	return false;
}

 

티셔츠와 카라를 매칭이 가능한지 여부를 확인하기 위한 함수

 

 

문제풀이

1. n, m 값을 입력 받고, T, K배열에 각각 티셔츠와 카라의 넓이를 입력 받아 저장해 준다.
2. n*m 범위의 for문을 통해 티셔츠에 카라를 조합할 수 있는 경우를 edges배열에 인접리스트로 추가해 준다.
3. 변수 ans를 0으로 초기화 하고, n번의 for문을 개행하고, 매 루프마다 t를 증가시켜 준다.
4. dfs함수에 현재 티셔츠 번호를 매개변수로 전달하고, 함수 내에선 해당 매개변수를 sn으로 받는다.
5. v[sn]이 t와 동일할 경우 이미 방문한 경우이므로 false를 리턴해 준다.
6. v[sn]에 t를 저장해 주고 sn의 인접 리스트를 순회해 준다.
7. 다음 요소를 변수 nn으로 초기화 하고 만약 M[nn]이 0일 경우 sn를 배정 후 true를 리턴한다.
8. 위 기저 조건에 걸리지 않은 경우 다시 한번 sn의 인접리스트를 순회해 준다.
9. dfs함수에 M[nn]을 매개변수로 전달하고 해당 리턴값이 true라면 M[nn]을 sn으로 저장 후 true를 리턴한다.
10. 위 두 기저조건에 해당하지 않을 경우 false를 리턴해 준다.
11. dfs함수의 최종 리턴값이 true인 경우 ans를 증가시켜 준다.
12. 모든 티셔츠에 대한 이분 매칭이 종료된 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 0-based-indexing을 사용했더니 M배열에 0번 티셔츠가 배정된 경우 배정되지 않았다고 판별이 되어 fail을 받았다.
2. 1-based-indexing으로 변경 하여 가장 첫 티셔츠가 1번으로 오게 하니 AC를 받았다.

 

참고 사항

• 인접 리스트를 만들 때 타입을 double로 명시하여 3/4, 5/4 등 나눗셈을 실수 형식으로 받아주어야 한다.

 

정답 코드

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

const int N = 201;
int T[N];
int K[N];
int n, m;
int M[N];
int v[N];
int t;
vector<int> edges[N];

bool dfs(int sn) {
	if (v[sn] == t) return false;
	v[sn] = t;

	for (int nn : edges[sn]) {
		if (!M[nn]) {
			M[nn] = sn;
			return true;
		}
	}

	for (int nn : edges[sn]) {
		if (dfs(M[nn])) {
			M[nn] = sn;
			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 >> T[i];
	for (int i = 1; i <= m; ++i) cin >> K[i];
	for (int i = 1; i <= n; ++i) {
		int tw = T[i];
		for (int j = 1; j <= m; ++j) {
			int kw = K[j];
			if (((double)tw / 2 <= kw && kw <= (double)tw * 3 / 4) || (tw <= kw && kw <= (double)tw * 5 / 4)) {
				edges[i].push_back(j);
			}
		}
	}

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