취미로 코딩하기

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

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

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

이 문제를 해결하는 것은 fake가 아닌, 정상적인 주제의 개수를 세는 것으로도 해결할 수 있다. 전체 신청수에서 정상 주제의 개수를 빼는 것으로 답을 구할 수 있기 때문이다. 아래의 설명은 정상적인 주제의 개수를 세는 방법을 다룬다.

먼저, 각 주제들의 첫번째 단어들을 포함하는 주제는 각각 하나 이상 있어야하고 두번째 단어들을 포함하는 주제 또한 각각 하나씩 있어야 한다는 점을 관찰하자. 이 때, 첫번째 단어끼리, 두번째 단어끼리는 중복이 없이 첫번째 단어들과 두번째 단어들로 이루어진 쌍을 먼저 최대한 많이 찾은 다음 나머지 쌍을 못 찾은 단어들의 주제를 하나씩 추가하는 것이 최선의 전략이 될 것이다. 이러한 쌍의 개수의 최댓값을 X라 하자.

각 주제들의 첫번째 단어들을 집합 A의 노드들로, 두번째 단어들을 집합 B의 노드들로 생각하고, sign-up sheet에 함께 적힌 집합 A와 B 주제들 사이에 에지를 그으면 이분그래프(Bipartite Graph)를 하나 얻을 수 있다. 이 이분그래프의 최대 이분매칭(Maximum Bipartite Matching)을 구하는 것으로 위에서 찾는 값 X를 구할 수 있다. 이를 이용해 문제를 해결하자.

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

#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();
	}
}