[백준] 9002 Match Maker

문제

baekjoon

해설

남자와 여자의 수가 n명으로 일치하고, 서로의 선호도를 리스트로 받기 때문에 gale-shapley 알고리즘으로 풀이할 수 있다.

코드

import sys
input = sys.stdin.readline

t = int(input())

def stable_marriage(men_preferences, women_preferences):
    n = len(men_preferences)
    free_men = list(range(n))
    women_partners = [None] * n 
    men_next_proposal = [0] * n 
    men_partners = [None] * n
    
    women_rankings = []
    for wp in women_preferences:
        ranking = [0] * n
        for i, man in enumerate(wp):
            ranking[man - 1] = i
        women_rankings.append(ranking)
    
    while free_men:
        man = free_men.pop(0)
        woman_index = men_next_proposal[man]
        woman = men_preferences[man][woman_index] - 1
        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 [w + 1 for w in men_partners]

for _ in range(t):
    n = int(input())
    men_pref, women_pref = [], []
    for pivot in (men_pref, women_pref):
        for _ in range(n):
            pivot.append(list(map(int, input().split())))

    matches = stable_marriage(men_pref, women_pref)
    print(*matches)