[BOJ 12022 // C++] 짝

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

 

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

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

12022번: 짝

주어진 문제는 Stable Marriage Problem(Stable Matching Problem; 이하 SMP)과 같다. SMP를 O(N^2)에 해결하는 알고리즘으로 Gale-Shapley 알고리즘이 잘 알려져있다.

 

이 문제에서의 Gale-Shapley 알고리즘이 어떻게 작동하는지를 간단히 서술하면 다음과 같다.

1. 예비 짝이 존재하지 않는 각 남자들이 아직 고백하지 않은 각자의 가장 높은 우선순위의 여자에게 고백을 한다.

2. 이전 단계에서 새로 고백받은 여자들은, 지금까지 받은 고백 중 가장 높은 우선순위의 남자와 예비 짝을 이루고, 만약 이 과정에서 이전에 예비 짝을 이룬 남자가 아닌 다른 남자와 짝을 이루게 될 경우 그 남자는 다시 예비 짝이 없는 상태로 바꾼다.

3. 모든 남자들이 예비 짝이 존재하지 않는다면 1로 돌아간다.

4. 알고리즘을 종료한다.

 

먼저, 모든 남자들이 짝을 이룰 때까지 고백을 반복하게 되므로 결국 모든 여자가 고백을 적어도 한번씩은 받게 될 수밖에 없다는 점을 관찰하자. 따라서 위 알고리즘이 종료되는 시점에서 모든 남자와 여자는 짝이 존재한다.

 

만약 어떤 남자A와 여자B가 위 알고리즘으로 구해진 각자의 짝보다 서로의 우선순위가 더 높다면, 남자A는 현재의 짝에게 고백을 하기 전에 여자B에게 먼저 고백을 했을 수밖에 없고, 그 고백을 여자B는 찼다는 뜻이므로 모순이 발생한다. 따라서 위 알고리즘으로 구해진 각자의 짝보다 서로의 우선순위가 더 높은 남녀의 쌍은 존재하지 않게 된다.

 

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

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

int MtoF[1001][1001];
int FtoM[1001][1001];
int iter[1001];
int matching[1001]; // F가 matching된 사람

int ans[1001];

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

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

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

	queue<int> que;
	for (int i = 1; i <= N; i++) {
		que.push(i);
	}

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

	for (int i = 1; i <= N; i++) ans[matching[i]] = i;

	for (int i = 1; i <= N; i++) cout << ans[i] << '\n';
}