[BOJ/Platinum 4] 백준 30976 사랑의 큐피드(C++)

문제 링크

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

 

문제

진주 나들이를 온 보선이는 목이 너무 말라서 경상국립대 앞에 있는 한 카페에 들어갔다. 그 카페에서는 진주교육대 여학생 N명과 연암공과대 남학생 M명이 모여서 미팅을 하고 있었다.

이 미팅에는 신기한 사실이 하나 있는데, 바로 미팅 중인 학생들의 상대에 대한 선호 여부는 키라는 요소 한 가지에만 영향을 받는다는 것이다. 구체적으로, 여학생들은 자신의 선호 기준보다 키가 작은 남학생만을 선호한다. 그리고 남학생들은 자신의 선호 기준보다 키가 큰 여학생만을 선호한다.

마침 이 카페에는 자칭 사랑의 큐피드 재혁이도 있었다. 이 미팅에 관심이 생긴 재혁이는 미팅 중인 테이블에서 오가는 얘기를 열심히 엿들어 미팅 중인 모든 학생들의 선호 기준을 파악했다. 그리고 재혁이는 자칭 사랑의 큐피드인 만큼 이 미팅에서 많은 커플이 생겼으면 하는 마음에 학생들을 직접 이어 주기로 결정했다.

이 모든 상황을 흥미롭게 바라보고 있던 보선이는 이 미팅에서 생길 수 있는 커플의 최대 수가 궁금해졌다. 이를 우리가 함께 알아보자. 이 문제에서의 커플은 서로 선호하는 여학생 1명과 남학생 1명으로 이루어진 집합을 의미하며, 한 학생이 둘 이상의 커플에 속할 수 없다.

 

입력

첫 번째 줄에는 여학생의 수 N, 남학생의 수 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 400)

두 번째 줄에는 G1, …, GN이 공백으로 구분되어 주어진다. Gi는 i번째 여학생의 키를 나타낸다. (1 ≤ Gi ≤ 300)

세 번째 줄에는 B1, …, BM이 공백으로 구분되어 주어진다. Bi는 i번째 남학생의 키를 나타낸다. (1 ≤ Bi ≤ 300)

네 번째 줄에는 L1, …, LN이 공백으로 구분되어 주어진다. Li는 i번째 여학생의 선호 기준을 나타낸다. (1 ≤ Li ≤ 300)

다섯 번째 줄에는 U1, …, UM이 공백으로 구분되어 주어진다. Ui는 i번째 남학생의 선호 기준을 나타낸다.(1 ≤ Ui ≤ 300)

입력으로 주어지는 모든 수는 정수이다.

 

출력

첫 번째 줄에 미팅에서 생길 수 있는 커플의 최대 수를 출력한다.

 

예제 입력 1

2 2
168 164
179 183
180 190
155 165

예제 출력 1

1

 

알고리즘 분류

• 이분 매칭

 

풀이

여학생을 기준으로, 여학생 각각이 선호하는 남학생을 기록해둔다.

물론 그 남학생 또한 해당 여학생을 선호해야 한다.

탄생할 수 있는 커플의 최대 개수를 구해야 하므로 이분 매칭 알고리즘을 이용한다.

DFS로 N명의 여학생을 남학생과 매칭한다. 여학생이 선호하는 남학생이 아직 커플이 되지 않았다면 둘을 커플로 매칭한다.

남학생이 커플로 매칭된 상태면, 그 남학생과 커플인 여학생에게 새로운 커플을 제안하기 위해 DFS를 수행하고, 새로운 커플이 맺어졌다면 현재 여학생과 남학생을 커플로 매칭한다.

아무튼 커플이 매칭되었다면 커플의 개수를 1 증가시킨다.

굳이 여학생을 기준으로 하는 이유는 여학생이 먼저 나와서이다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 401
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
int G[MAX], B[MAX], L[MAX], U[MAX];
vector<int> Girls[MAX];
int LMatch[MAX], RMatch[MAX];
bool Visited[MAX];
int Answer;

void init() {
	for (int i = 0; i < MAX; i++) {
		LMatch[i] = -1;
		RMatch[i] = -1;
	}
}

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> G[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> B[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> L[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> U[i];
	}
}

bool dfs(int Girl) {
	for (int i = 0; i < (int)Girls[Girl].size(); i++) {
		int Boy = Girls[Girl][i];
		if (!Visited[Boy]) {
			Visited[Boy] = true;
			if ((RMatch[Boy] == -1) || dfs(RMatch[Boy])) {
				RMatch[Boy] = Girl;
				LMatch[Girl] = Boy;
				return true;
			}
		}
	}

	return false;
}

void settings() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if ((B[j] < L[i]) && (G[i] > U[j])) {
				Girls[i].push_back(j);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < MAX; j++) {
			Visited[j] = false;
		}
		if (dfs(i)) {
			Answer++;
		}
	}
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
    FASTIO

	init();
	input();
	settings();
	printAnswer();

    return 0;
}