[P4] 백준 17481번 최애 정하기 C++ 이분 매칭, 해시맵

리뷰

 

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

문자열로 들어오는 이름을 해시맵으로 인덱싱해 이분 매칭의 최대 값을 구하는 문제

 

 

전역 변수

• N : 친구 관련 배열의 최대 크기를 정의할 상수 변수
• M : 최애 멤버 관련 배열의 최대 크기를 정의할 상수 변수
• n : 친구의 수를 저장할 변수
• m : 최애 멤버의 수를 저장할 변수
• c : 친구가 좋아하는 최애 멤버의 수를 저장할 변수
• ans : 친구와 최애 멤버가 매칭된 수를 저장할 변수
• name : 최애 멤버의 이름을 저장할 변수
• idx : 최애 멤버를 정수형 인덱스로 저장하기 위한 해시맵
• 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 (!mat[next]) {
			mat[next] = node;
			return true;
		}
	}

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

 

친구가 좋아하는 최애 멤버를 매칭 시켜주기 위한 함수

 

문제풀이

1. n, m값을 입력 받고 m명의 최애 아이돌의 이름을 입력 받은 후 해시맵 idx을 통해 정수 인덱싱 해준다.
2. 1~n번 친구가 좋아하는 최애 아이돌의 이름을 입력 받은 후 정수로 파싱하여 edges배열에 추가해 준다.
3. 1~n번 친구를 순회하며 매 친구마다 t를 증가시키고 dfs함수에 현재 친구의 번호를 전달하여 수행한다.
4. dfs함수의 리턴값이 true라면 ans를 증가시킨다.
5. 모든 탐색을 마친 후 ans와 n이 같다면 "YES"를, 아니라면 "NO"를 출력 및 줄바꿈 후 ans를 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

• 처음엔 dfs를 할 때 문자열을 직접 참고하려 했으나 문자열을 정수형으로 인덱싱하면 훨씬 더 편하고 쉽다.

 

정답 코드

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

const int N = 1001;
const int M = 1001;
int n, m, c, ans;
string name;
unordered_map<string, int> idx;
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 (!mat[next]) {
			mat[next] = node;
			return true;
		}
	}

	for (int next : edges[node]) {
		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 <= m; ++i) {
		cin >> name;
		idx[name] = i;
	}

	for (int i = 1; i <= n; ++i) {
		cin >> c;
		while (c--) {
			cin >> name;
			edges[i].push_back(idx[name]);
		}
	}

	for (int i = 1; i <= n; ++i) {
		t++;
		if (dfs(i)) ans++;
	}
	
	if (ans == n) cout << "YES";
	else cout << "NO\n" << ans;
}