[BOJ 12843 // C++] 복수전공

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

 

이번에 볼 문제는 백준 12843번 문제인 복수전공이다.
문제는 아래 링크를 확인하자.

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

 

"두 학부 간의", 즉 "두 학부 사이의" 겹치는 내용이 존재하는 강의 사이의 관계들이 입력으로 주어지므로, 같은 학부의 강의들 사이의 관계는 주어지지 않음을 관찰하자. 따라서 주어지는 과목들을 노드로, 관계를 에지로 하여 주어진 문제 상황을 그래프로 모델링하면 해당 그래프는 컴퓨터 학부 강의들의 집합과 소프트웨어 학부 강의들의 집합 사이에만 에지가 존재하는 이분그래프(bipartite graph)가 됨을 알 수 있다. 또한, 문제에서 구하고자하는 값은 해당 그래프에서 어떤 에지도 양 끝의 두 노드를 선택하지 않게끔 가장 많은 노드를 고를 때의 그 고른 노드 수와 같음을 알 수 있다. 즉, 이 문제는 이분그래프에서의 maximum independent set의 크기를 구하는 문제와 같음을 알 수 있다.

 

이분그래프에서의 maximum independent set의 크기는 전체 노드의 수에서 maximum bipartite matching의 수를 뺀 것과 같음은 잘 알려져있다. Kőnig's theorem(쾨니그의 정리)와 "maximum independet set과 minimum vertex cover 사이의 관계"를 이용하면 증명도 어렵지 않으므로 관련 내용을 잘 모른다면 이번에 알아보도록 하자.

 

위 내용을 이용해 문제를 해결하자.

 

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

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

int N, A, B, M;
vector<int> G[2001];
int idtoidx[2001];
int matching[2001];
int visited[2001];

int dfs(int cur) {
	visited[cur] = 1;
	for (auto &nxt:G[cur]) {
		if (!matching[nxt]) {
			matching[nxt] = cur;
			return 1;
		}
		else if (!visited[matching[nxt]] && dfs(matching[nxt])) {
			matching[nxt] = cur;
			return 1;
		}
	}
	return 0;
}

int ans;

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		int id; char c; cin >> id >> c;
		if (c == 'c') {
			A++;
			idtoidx[id] = A;
		}
		else {
			B++;
			idtoidx[id] = B + 2000;
		}
	}
	while (M--) {
		int x, y; cin >> x >> y;
		x = idtoidx[x], y = idtoidx[y];
		if (x > y) swap(x, y);
		G[x].emplace_back(y - 2000);
	}

	for (int i = 1; i <= A; i++) {
		memset(visited, 0, sizeof(visited));
		ans += dfs(i);
	}

	cout << N - ans;
}