취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14373번 문제인 Technobabble (Small)이다.
문제는 아래 링크를 확인하자.

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

14374번 문제(링크)에서 입력이 작아진 형태이다. 해당 문제의 풀이를 참고해 문제를 해결하자.

주어지는 데이터의 크기가 충분히 작으므로, "fake가 아닌 신청"이 무엇이었을지 모든 조합의 경우의 수에 대하여 각각 탐색해보는 완전탐색 알고리즘을 구현해 문제를 해결할 수도 있을 것이다.

아래는 제출한 소스코드이다.

#define NODE 1001
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
using namespace std;

int N;
vector<int> G[NODE];
int visited[NODE];
int matching[NODE];

int bpfunc(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto& node : G[current]) {
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		if (bpfunc(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

int bipartitematching() {
	int ret = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		ret += bpfunc(i);
	}

	return ret;
}

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

	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		memset(matching, 0, sizeof(matching));
		map<string, int> mpL, mpR;
		int idxL = 0, idxR = 0;
		int K; cin >> K;
		for (int k = 0; k < K; k++) {
			string s1, s2; cin >> s1 >> s2;
			if (!mpL.count(s1)) mpL.insert(make_pair(s1, ++idxL));
			if (!mpR.count(s2)) mpR.insert(make_pair(s2, ++idxR));
			int iL = mpL[s1], iR = mpR[s2];
			G[iL].emplace_back(iR);
		}


		N = idxL;

		int cnt = bipartitematching();
		cout << "Case #" << t << ": " << K - (cnt + (idxL - cnt) + (idxR - cnt)) << '\n';

		for (int i = 1; i <= idxL; i++) G[i].clear();
	}
}