취미로 코딩하기

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

이번에 볼 문제는 백준 2016번 문제인 미팅 주선하기이다.
문제는 아래 링크를 확인하자.

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

태현이의 각 여학생에 대한 선호도 순위의 각 permutation 중 문제에서 주어진 알고리즘의 결과로 얻어지는 태현이의 짝 중 원래의 선호도로 제출했을 때보다 더 나은 결과를 얻을 수 있는 permutation이 존재하는지를 판단하는 문제이다.

각 permutation에 대하여 주어진 알고리즘을 돌렸을 때의 짝을 전부 구해보는 완전탐색을 통해 문제를 해결하자. 큐 등의 자료구조와 algorithm 헤더의 next_permutation 등을 이용하면 구현을 편하게 할 수 있다.

여담으로 지문에서 제시된 알고리즘은 남학생과 여학생 사이의 female-optimal한 stable matching을 찾는 Gale-Shapley 알고리즘과 같다. 이 과정에 대해 더 궁금한 점이 있다면 stable matching 또는 Gale-Shapley 알고리즘에 대해 공부하는 것을 추천한다.

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

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

int T;
int MtoF[6][6];
int FtoM[6][6];
int iter[6];
int matching[6]; // M에게 matching된 사람

int ans[1001];

int func() {
	memset(iter, 0, sizeof(iter));
	memset(matching, 0, sizeof(matching));
	queue<int> que;
	for (int i = 1; i < 6; i++) que.push(i);

	while (!que.empty()) {
		int curF = que.front(); que.pop();
		int curM = FtoM[curF][++iter[curF]];
		int& matchingM = matching[curM];
		if (matchingM == 0) matchingM = curF;
		else if (MtoF[curM][curF] < MtoF[curM][matchingM]) {
			que.push(matchingM);
			matchingM = curF;
		}
		else que.push(curF);
	}

	return matching[1];
}

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

	cin >> T;
	while (T--) {
		for (int j = 1; j < 6; j++) MtoF[1][j] = j;
		for (int i = 2; i < 6; i++) {
			for (int j = 1; j < 6; j++) {
				int x; cin >> x;
				MtoF[i][x - 5] = j;
			}
		}

		for (int i = 1; i < 6; i++) {
			for (int j = 1; j < 6; j++) {
				int x; cin >> x;
				FtoM[i][j] = x;
			}
		}

		int val = func();
		bool chk = 0;

		for (int k = 1; k < 120; k++) {
			next_permutation(MtoF[1], MtoF[1] + 6);
			if (func() < val) chk = 1;
		}

		if (chk) cout << "YES\n";
		else cout << "NO\n";
	}
}