취미로 코딩하기

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

이번에 볼 문제는 백준 21219번 문제인 Restaurants이다.
문제는 아래 링크를 확인하자.

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

이 문제는 Stable Matching에 대한 기본 정리인 Rural Hospital Theorem을 이용하는 문제이다. 이 문제의 상황에 맞춰 서술된 정리의 내용은 다음과 같다.

만약 손님의 각 레스토랑에 대한 우선순위와 레스토랑의 각 손님에 대한 우선순위가 strict하다면, 손님과 레스토랑 사이의 stable matching은 아래와 같은 성질을 갖는다.
1. "matching이 이루어지는 손님의 집합", "각 레스토랑마다 받게 되는 손님의 수"는 모든 stable matching에서 일정하다.
2. 정원을 모두 채우지 못한 각 레스토랑의 경우, "그 레스토랑이 받은 손님의 집합"은 모든 stable matching에서 일정하다.

또한, 이와 같은 경우의 stable matching은 Gale-Shapley 알고리즘과 동일한 원리의 알고리즘으로 항상 찾아낼 수 있다.

Rural Hospital Theorem과 Gale-Shapley 알고리즘을 이용해 하나의 stable matching을 찾아낸 후 그 matching에 포함된 손님의 집합을 출력하는 것으로 문제를 해결하자.

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

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

int C, R;
int reserv[10001];
vector<int> CtoR[50001];
map<pair<int, int>, int> RtoC;
int iter[50001];
priority_queue<pair<int, int>> matching[10001]; // {우선도, 손님}

vector<int> ans;

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

	cin >> C >> R;
	for (int r = 1; r <= R; r++) cin >> reserv[r];

	string s; getline(cin, s);
	for (int c = 1; c <= C; c++) {
		getline(cin, s);
		s += ' ';
		int tmp = 0;
		for (auto l : s) {
			if (l == ' ') {
				CtoR[c].emplace_back(tmp);
				tmp = 0;
			}
			else tmp = tmp * 10 + (l - '0');
		}
	}
	for (int r = 1; r <= R; r++) {
		getline(cin, s);
		s += ' ';
		int tmp = 0;
		int priority = 1;
		for (auto l : s) {
			if (l == ' ') {
				RtoC.insert(make_pair(make_pair(r, tmp), priority++));
				tmp = 0;
			}
			else tmp = tmp * 10 + (l - '0');
		}
	}

	queue<int> que;
	for (int c = 1; c <= C; c++) que.push(c);

	while (!que.empty()) {
		int curC = que.front(); que.pop();
		if (CtoR[curC].size() == iter[curC]) continue;
		
		int curR = CtoR[curC][iter[curC]++];
		auto& matchingcurR = matching[curR];
		matchingcurR.push(make_pair(RtoC[make_pair(curR, curC)], curC));
		if ((int)matchingcurR.size() > reserv[curR]) {
			que.push(matchingcurR.top().second);
			matchingcurR.pop();
		}
	}

	for (int r = 1; r <= R; r++) {
		while (!matching[r].empty()) {
			ans.emplace_back(matching[r].top().second);
			matching[r].pop();
		}
	}

	sort(ans.begin(), ans.end());

	for (auto x : ans) cout << x << '\n';
}