[백준] 20009 형곤이의 소개팅

문제

Backjoon

해설

gale-shapley 알고리즘을 통해 풀이할 수 있다. 파이썬 코드는 아래와 같다.

코드

import sys
input = sys.stdin.readline

n = int(input())

men = input().split()
women = input().split()
men_prefs, women_prefs = {}, {}
for pivot in (men_prefs, women_prefs):
    for _ in range(n):
        people = input().split()
        pivot[people[0]] = people[1:]

def stable_marriage(men_prefs, women_prefs):
    men = list(men_prefs.keys())
    women = list(women_prefs.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 = {}
    for woman, prefs in women_prefs.items():
        ranking = {man: rank for rank, man in enumerate(prefs)}
        women_rankings[woman] = ranking

    while free_men:
        man = free_men.pop(0)
        woman = men_prefs[man][men_next_proposal[man]]
        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)

    result = []
    for man, woman in men_partners.items():
        result.append((man, woman))
    return result

matching = stable_marriage(men_prefs, women_prefs)

for man, woman in matching:
    print(man, woman)