이 글에서는 주어진 특정 사례에 대한 매칭 문제(안정 결혼 문제, Stable Marriage Problem)를 해결하는 C++ 프로그램을 소개합니다. N명의 남성과 N명의 여성이 있으며, 각 사람은 반대 성별의 모든 상대를 선호도 순서대로 순위를 매겼습니다. 목표는 현재 파트너보다 서로를 더 선호하는 이성 간의 짝이 존재하지 않도록 남녀를 결혼시키는 것입니다. 이러한 경우가 하나도 없다면, 모든 결혼은 '안정적(stable)'이라고 표현합니다.
알고리즘 개요
이 프로그램은 데이비드 게일(David Gale)과 로이드 섀플리(Lloyd Shapley)가 제안한 게일-섀플리(Gale-Shapley) 알고리즘을 기반으로 동작합니다. 전체 흐름은 다음과 같습니다.
시작
함수 WomenPrefersMenOverMen1():
A) 여성이 현재 약혼자(m1)보다 새로운 남성(m)을 더 선호하는지 확인
B) 여성의 선호 목록에서 m1이 m보다 앞에 있다면, 현재 약혼 관계를 유지
C) 여성의 선호 목록에서 m이 m1보다 앞에 있다면, 기존 약혼을 파기하고 m과 새로 약혼
종료
시작
함수 stablewedding():
1) 남성에게 0부터 N-1까지 번호를 부여
2) 여성에게 N부터 2N-1까지 번호를 부여
3) 자유 상태인 남성이 존재하는 동안 반복
A) 첫 번째 자유 남성을 선택
B) 해당 남성의 선호도 순서대로 여성들을 차례로 방문
C) 선호하는 여성이 자유 상태라면, 두 사람은 파트너가 됨
D) 여성이 이미 약혼 상태라면, 현재 약혼 상대를 확인
E) 여성이 현재 약혼자(m1)보다 새 남성(m)을 더 선호한다면,
기존 약혼을 파기하고 m과 새로 약혼
종료C++ 구현 예제
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define N 4
bool WomenPrefersMenOverMen1(int prefer[2*N][N], int w, int m, int m1) {
for (int i = 0; i < N; i++) {
if (prefer[w][i] == m1)
return true;
if (prefer[w][i] == m)
return false;
}
}
void stablewedding(int prefer[2*N][N]) {
int wPartner[N]; // 여성의 파트너를 저장할 배열 초기화
bool mFree[N]; // 남성의 가용 여부를 저장할 배열 초기화
// 모든 남성과 여성을 자유 상태로 초기화
memset(wPartner, -1, sizeof(wPartner));
memset(mFree, false, sizeof(mFree));
int freeCnt = N;
while (freeCnt > 0) { // 자유 상태인 남성이 있는 동안 반복
int m; // 첫 번째 자유 남성 선택
// 자유 남성의 선호도에 따라 여성들을 차례로 방문
for (m = 0; m < N; m++)
if (mFree[m] == false)
break;
for (int i = 0; i < N && mFree[m] == false; i++) {
int w = prefer[m][i];
// 선호하는 여성이 자유 상태라면, 두 사람은 파트너가 됨
if (wPartner[w-N] == -1) {
wPartner[w-N] = m;
mFree[m] = true;
freeCnt--;
} else { // 여성이 자유 상태가 아니라면
// 여성의 현재 약혼 상대를 확인
int m1 = wPartner[w-N];
// 여성이 현재 약혼자(m1)보다 새 남성(m)을 더 선호한다면,
// 기존 약혼을 파기하고 m과 새로 약혼
if (WomenPrefersMenOverMen1(prefer, w, m, m1) == false) {
wPartner[w-N] = m;
mFree[m] = true;
mFree[m1] = false;
}
}
}
}
cout << "Woman Man" << endl;
for (int i = 0; i < N; i++)
cout << " " << i+N << "\t" << wPartner[i] << endl;
}
int main() {
int p[2*N][N] = {
{7, 5, 6, 4},
{5, 4, 7, 6},
{4, 5, 7, 6},
{4, 5, 7, 6},
{0, 1, 3, 2},
{0, 1, 3, 2},
{0, 1, 3, 2},
{0, 1, 3, 2},
};
stablewedding(p);
return 0;
}실행 결과
Woman Man 4 3 5 1 6 2 7 0
동작 원리 설명
프로그램에서 사용되는 주요 변수는 다음과 같습니다.
wPartner[N]: 각 여성의 현재 파트너(남성 번호)를 저장하는 배열입니다. 초기값은 -1로 설정되어, 누구와도 약혼하지 않은 상태를 의미합니다.mFree[N]: 각 남성이 자유 상태인지 여부를 저장하는 불리언 배열입니다.freeCnt: 아직 파트너가 정해지지 않은 남성의 수를 추적하며, 0이 되면 알고리즘이 종료됩니다.
배열 p에는 선호도 정보가 담겨 있습니다. 인덱스 0~3은 남성들의 여성 선호 목록이고, 인덱스 4~7은 여성들의 남성 선호 목록입니다. 모든 남성이 파트너를 찾을 때까지 매칭 과정을 반복한 뒤, 최종적으로 안정적인 결혼 조합을 출력합니다. 이 알고리즘의 시간 복잡도는 최악의 경우 O(N²)이며, 항상 안정적인 매칭 결과를 보장한다는 것이 수학적으로 증명되어 있습니다.