[백준] 3761 The Stable Marriage Problem

문제

안정 결혼 문제를 푸는 알고리즘을 구현하는 것이다. 안정 결혼 문제(Stable Marriage Problem)은 예전부터 제시됐던 문제이다. 남자와 여자가 각각 n명으로 같은 수의 집합이 주어지고, 서로 원하는 상대방에 대한 선호도를 리스트로 가지고 있다.

 

이를 해결하기 위한 도전은 안정 매칭(Stable Matching)을 모두 구현해야 한다. 안정 매칭이란 일대일로 남자와 여자를 매칭하는데, f ∈ F가 현재 파트너보다 m ∈ M을 선호하고 m이 현재 파트너보다 f를 선호하는 쌍(m, f)이 없는 경우 매칭을 안정적이라고 합니다. 다른 안정된 결혼 B가 없는 경우, 어떤 남성이든 A에 배정된 여성보다 더 선호하는 여성과 짝을 이루는 안정된 결혼 A를 남성 최적이라고 합니다. 

선호하는 남성과 여성의 목록이 주어지면 남성 최적 안정 결혼을 찾아야 합니다.

해설

안정 결혼 문제의 제시는 예전부터 제시되어왔다. 이러한 알고리즘을 풀기 위해서는 gale-shapley 알고리즘을 사용하여 풀 수 있다. 1962년에 게일과 샤플리가 안정 결혼 문제를 푸는 최적해를 증명해, 이러한 알고리즘을 게일-샤플리 알고리즘이라고 부른다.

코드

import sys
input = sys.stdin.readline

def stable_marriage(men_preferences, women_preferences):
    men = list(men_preferences.keys())
    women = list(women_preferences.keys())
    n = len(men)
    
    free_men = men[:]
    women_partners = {woman: None for woman in women}
    men_next_proposal = {man: 0 for man in men}
    men_partners = {man: None for man in men}
    
    women_rankings = {woman: {} for woman in women}
    for woman, wp in women_preferences.items():
        for i, man in enumerate(wp):
            women_rankings[woman][man] = i
    
    while free_men:
        man = free_men.pop(0)
        woman_index = men_next_proposal[man]
        woman = men_preferences[man][woman_index]
        men_next_proposal[man] += 1
        
        if women_partners[woman] is None:
            women_partners[woman] = man
            men_partners[man] = woman
        else:
            current_partner = women_partners[woman]
            if women_rankings[woman][man] < women_rankings[woman][current_partner]:
                women_partners[woman] = man
                men_partners[man] = woman
                free_men.append(current_partner)
            else:
                free_men.append(man)
    
    return sorted([[man, men_partners[man]] for man in men])

t = int(input())

for i in range(t):
    n = int(input())
    people = input().split()
    men, women = {}, {}
    
    for _ in range(n):
        pivot, prefs = input().strip().split(':')
        men[pivot] = prefs.strip()
    
    for _ in range(n):
        pivot, prefs = input().strip().split(':')
        women[pivot] = prefs.strip()
    
    matches = stable_marriage(men, women)
    
    for match in matches:
        print(match[0], match[1])
    
    if i < t - 1:
        print()