[P4] 백준 22742번 Make Friendships C++ 정렬, 값 압축, 이분 매칭

리뷰

 

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

값 제한을 전달해 주지 않는 불친절할 문제!!

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• vi : 값->인덱스 변환을 위한 해시맵
• iv : 인덱스->값 변환을 위한 벡터
• edges : 인접 리스트를 저장할 정수형 벡터 배열
• n : 친구의 수를 저장할 변수
• m : 가능한 날의 개수를 저장할 변수
• v : 이분 매칭 시 방문 시간을 추적하기 위한 정수형 벡터
• match : 매칭된 일자를 저장할 정수형 벡터
• t : 현재 탐색 시간을 저장할 변수

 

함수

1. dfs

bool dfs(int cn) {
	for (int nn : edges[cn]) {
		if (match[nn] == -1) {
			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값을 입력 받는다. 만약 n이 0이라면 break처리한다.
2. m값을 입력 받고, 이전 테스트 케이스에서 사용했던 자료구조, 변수들을 초기화해준다.
3. 아이작의 m개 일정을 입력 받아 벡터 iv를 초기화한다.
4. sort함수를 통해 iv를 오름차순으로 정렬하고, erase, unique함수를 통해 중복을 제거한다.
5. m에 중복 제거 후 iv의 size를 저장한다.
6. v를 m크기로, 값은 0인 상태로 초기화한다.
7. match를 m크기로, 값은 -1인 상태로 초기화한다.
8. iv를 순회하며 해시맵 vi에 값별 인덱스를 저장하여 초기화한다.
9. n명의 친구를 순회하며 각 친구마다 일정을 입력 받아, 아이작과 동일한 일정만 남겨 edges배열을 초기화한다.
10. 변수 ans를 0으로 초기화하고, 이분 매칭을 수행하여, 매칭된 횟수만큼 ans를 증가시킨다.
11. ans에 저장된 값을 출력하고, 개행문자를 삽입하여 줄 바꿈을 수행한다.
12. 테스트케이스가 종료될때까지 위 로직을 반복한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. M값의 제한, 일자의 상한값, 일자 중복 여부에 대한 내용을 문제에서 제공해주지 않는다.

 

정답 코드

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

const int N = 1e3;
unordered_map<int, int> vi;
vector<int> iv;
vector<int> edges[N];
int n, m;
vector<int> v;
vector<int> match;
int t;

bool dfs(int cn) {
	for (int nn : edges[cn]) {
		if (match[nn] == -1) {
			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);

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

		cin >> m;
		vi.clear();
		iv.clear();
		v.clear();
		match.clear();
		t = 0;

		for (int i = 0; i < m; ++i) {
			int d; cin >> d;
			iv.push_back(d);
		}
		sort(iv.begin(), iv.end());
		iv.erase(unique(iv.begin(), iv.end()), iv.end());
		m = iv.size();
		v.resize(m, 0);
		match.resize(m, -1);
		
		for (int i = 0; i < m; ++i) vi[iv[i]] = i;		

		for (int i = 0; i < n; ++i) {
			int c; cin >> c;
			edges[i].clear();

			vector<int> edge;
			while (c--) {
				int d; cin >> d;
				if (!vi.count(d)) continue;

				int idx = vi[d];
				edge.push_back(idx);
			}
			sort(edge.begin(), edge.end());
			edge.erase(unique(edge.begin(), edge.end()), edge.end());
			edges[i] = edge;
		}

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