BAEKJOON 9002번: Match Maker

https://www.acmicpc.net/problem/9002

9002번: Match Maker

풀이

여자와 남자를 정점으로 하고 모든 여자와 남자를 간선으로 이으면 이는 이분 그래프를 띤다.

안정된 매칭을 만들기 위해서 아래와 같은 방법을 따라 매칭을 형성하면 된다.

 

1. 한 남자를 선호도가 가장 높은 여자와 매칭

2. 여자가 이미 매칭되었다면 여자의 선호도에 따라 매칭 할지 말지 결정

3. 이미 매칭된 여자와 남자가 매칭되었다면 원래 그 여자와 매칭되어있던 남자는 선호도가 높은 순으로 위 과정 반복

 

위 순서대로 작동하는 코드를 구현하면 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int M[203][203],W[203][203],m[103],w[203],N;
void f(){
    memset(m,-1,sizeof(m));
    memset(w,-1,sizeof(w));
    queue<int>q;
    for(int i=1;i<=N;i++)q.push(i);
    while(!q.empty()){
        int qf=q.front();
        for(int j=101;j<=N+100;j++){
            int i=M[qf][j];
            if(w[i]==-1){
                m[qf]=i;
                w[i]=qf;
                break;
            }else{
                if(W[i][qf]<W[i][w[i]]){
                    m[qf]=i;
                    m[w[i]]=-1;
                    q.push(w[i]);
                    w[i]=qf;
                    break;
                }else{
                    continue;
                }
            }
        }
        q.pop();
    }
}
int main(){
    int T,q;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        memset(M,0,sizeof(M));
        memset(W,0,sizeof(W));
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                scanf("%d",&q);
                M[i][j+100]=q+100;
            }
        }
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                scanf("%d",&q);
                W[100+i][q]=j;
            }
        }
        f();
        for(int i=1;i<=N;i++)printf("%d ",m[i]-100);
        printf("\n");
    }
    return 0;
}