152. Stable Marriage Problem

안정적인 결혼 문제(Stable Marriage Problem, SMP)는 크기가 동일한 두 집합에서 안정적인 매칭(Stable Matching)을 찾는 문제이다. 두 집합 간의 안정적인 매칭이라는 것은 다음과 같다.

• 각 집합의 원소는 상대 집합의 원소들에 대한 서로 다른 선호도를 가진다.
• 첫 번째 집합과 두 번째 집합의 원소가 일대일로 매칭되어 있다.
• 첫 번째 집합에 속한 원소 $A$, $B$가 두 번째 집합에 속한 원소 $C$, $D$와 각각 매칭되어 있을 때 $A$가 $C$보다 $D$를 선호하면서 $D$가 $B$보다 $A$를 선호하는 경우는 존재하지 않는다.

세 번째 조건을 다시 설명하면 서로 매칭되지 않은 두 원소 모두가 상대 원소를 자신과 매칭된 원소보다 더 선호하는 경우가 존재하지 않는다는 것이다. 이것을 일반적으로 남성과 여성 커플에 비유하므로 안정적인 결혼 문제라는 이름이 붙게 되었다.

---

안정적인 결혼 문제를 해결하는 방법으로는 Gale-Shapley Algorithm(Deferred Acceptance Algorithm, Propose-and-Reject Algorithm)이 알려져 있다. 이 알고리즘은 다음과 같은 방법으로 작동한다.

    1. 첫 번째 집합에서 매칭되지 않은 원소 $u$를 하나 고른다.

    2. 두 번째 집합에서 아직 $u$와 매칭을 시도한 적이 없는 원소 중 $u$가 가장 선호하는 원소 $v$를 찾는다.

    3. $u$와 $v$의 매칭을 시도한다. $v$가 매칭되지 않았거나 $v$와 매칭된 원소보다 $u$를 더 선호하는 경우 $u$와 $v$를 매칭한다. $v$와 매칭된 원소가 바뀐 경우 기존에 $v$와 매칭된 원소는 매칭되지 않은 상태가 된다.

    4. 모든 원소가 매칭될 때까지 위의 과정을 반복한다.

 

이 알고리즘의 정당성을 증명하기 위해서는 세 가지를 확인해야 한다.

    1. 알고리즘이 유한한 시간 안에 종료된다.

    2. 두 집합의 모든 원소가 매칭된다.

    3. 구한 매칭이 안정적인 매칭의 조건을 만족한다.

 

집합의 크기가 $n$일 때 두 집합에서 원소를 하나씩 선택하는 경우의 수는 $n^2$이고, 이 쌍들을 최대 한 번씩만 매칭하기 때문에 매칭 시도는 유한한 횟수만큼 발생한다. 또한 첫 번째 집합의 원소가 두 번째 집합의 모든 원소와 매칭을 시도할 수 있으므로 아직 매칭되지 않은 원소와 매칭을 시도할 경우 매칭이 되어야 한다. 따라서 매칭이 안 되는 경우는 발생하지 않는다. 마지막으로 구한 매칭이 안정적인 매칭이라는 것은 다음과 같은 방법으로 보일 수 있다.

• 첫 번째 집합의 원소 $A$, $B$가 두 번째 집합의 원소 $C$, $D$와 각각 매칭되어 있고, $A$가 $C$보다 $D$를 선호하고 $D$가 $B$보다 $A$를 선호한다고 가정하자.
• $A$는 선호도가 높은 순서대로 매칭을 시도하므로 $D$를 $C$보다 먼저 매칭하려고 시도한다.
• $A$가 $D$와 매칭된 경우, $A$가 $C$와 매칭을 시도하거나 $B$가 $D$와 매칭을 시도할 때 기존의 매칭이 끊어지지 않는다.
• $A$가 $D$와 매칭되지 않은 경우 $D$가 $A$보다 선호하는 원소와 이미 매칭된 것이다. 이 경우 $B$가 $D$와 매칭을 시도할 때 기존의 매칭이 끊어지지 않는다.
• 두 경우 모두 $A$와 $C$가 매칭되고 $B$와 $D$가 매칭되는 상황에 도달하지 않으므로 모순이 발생한다.
• 따라서 처음의 가정과 같은 상황은 발생하지 않는다.

 

구현은 다음과 같다. 이 유형은 입력의 형태가 다양하게 나올 수 있으므로 때때로 주의해야 한다.

#import<bits/stdc++.h>
using namespace std;
int p[1005], x[1005], y[1005], a[1005][1005], b[1005][1005];
int main()
{
    int k, n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)cin >> a[i][j]; // 첫 번째 그룹의 i번 원소가 두 번째 그룹의 a[i][j]번 원소를 j번째로 선호함
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> k;
            b[i][k] = j; // 두 번째 그룹의 i번 원소가 첫 번째 그룹의 k번 원소를 b[i][k]번째로 선호함
        }
    }
    for(int t = 1; t <= n; t++) // 첫 번째 그룹의 각각의 원소들은 최대 n번 매칭을 시도함
    {
        for(int i = 1; i <= n; i++)
        {
            if(x[i])continue; // 첫 번째 그룹의 i번 원소가 매칭된 경우
            for(; ++p[i]; )
            {
                int w = a[i][p[i]]; // i번 원소가 다음으로 매칭을 시도할 두 번째 그룹의 원소
                if(!y[w]) // w번 원소가 아직 매칭되지 않은 경우
                {
                    x[i] = w;
                    y[w] = i;
                    break;
                }
                if(b[w][i] < b[w][y[w]]) // w번 원소가 현재 매칭된 원소보다 i번 원소를 더 선호하는 경우
                {
                    x[i] = w;
                    x[y[w]] = 0;
                    y[w] = i;
                    break;
                }
            }
        }
    }
}

$x[i]$에는 첫 번째 집합의 $i$번째 원소와 매칭된 두 번째 집합의 원소, $y[i]$에는 두 번째 집합의 $i$번째 원소와 매칭된 첫 번째 집합의 원소가 저장된다.

 

[참고 링크]

 

Stable Marriage Problem

Gale-Shapely Algorithm

 

[연습문제]

 

BOJ 12022. 짝 (Platinum I)

남자 그룹과 여자 그룹의 안정적인 매칭을 구한다.

 

BOJ 21219. Restaurants (Diamond V)

레스토랑과 손님의 안정적인 매칭을 구하는데, 하나의 레스토랑이 여러 손님을 받을 수도 있고 레스토랑을 못 정하는 손님이 생길 수도 있어서 추가적인 처리가 필요하다. 입력이 빈 줄을 포함할 수도 있으므로 주의해야 한다.

 

→ solved.ac tag: stable_marriage