백준 17481, 최애 정하기

개요

문제 링크
플래 4, Graph, Bipartite matching
N명의 사람이 M명의 최애가 있을 때 최대한 많은 사람이 최애를 선택하게 만들기

---

접근

1. 이분매칭 을 사용하는 살짝 씹덕틱한 문제. 다른 이분매칭 문제와 마찬가지로 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다.
2. N개의 사람 그룹과, M개의 최애 그룹이 있고, 그래프의 모든 연결관계는 최애와 사람을 연결하므로 이분 그래프의 매칭 문제가 된다.
3. 엥 그런데 이분매칭은 정수로 하는거 아님? 이럴 때는 고민말고 C++의 미친장점, map을 쓰면 된다. map에는 각 이름의 맞는 index를 저장해둔다.
4. 나머지는 이분매칭을 잘 이해하고 있다면 크게 어렵지 않다. 원하는 최애 중 아직 아무도 선택 안했거나, 원래 사람을 내쫓을 수 있으면 자기가 선택하면 된다.

---

Pseudo code

can(a) {
    // 최애 중 선택할 건데
    for (b:graph[a])
        // 아무도 선택 안했거나
        // 원래 선택한 사람을 내쫓을 수 있을 때
        if (!B[b]||can(B[b])) {
            A[a]=b,B[b]=a
            return 1
        }
    return 0
}

match() {
    cnt=0
    for (i = 1~n)
        if (!A[i])
            cnt += can(i)
    return cnt
}

---

Source code

#include <iostream>
#include <vector>
#include <map>
using namespace std;

#define N 1010
#define vec vector
#define str string
#define pb push_back
int A[N],B[N];
bool vis[N];
vec<int> adj[N];

bool can(int a) {
    vis[a]=1;
    for (auto b:adj[a]) {
        if (!B[b]||!vis[B[b]]&&can(B[b])) {
            A[a]=b,B[b]=a;
            return 1;
        }
    }
    return 0;
}

map <str,int> name;
int main() {
    int n,m,k,x;
    cin>>n>>m;
    str s;
    for (int i=1;i<=m;i++)
        cin>>s,name[s]=i;
    for (int i=1;i<=n;i++) {
        cin>>k;
        while(k--)
            cin>>s,adj[i].pb(name[s]);
    }
    int cnt=0;
    for (int i=1;i<=n;i++)
        if (!A[i]) {
            fill(vis,vis+N,0);
            cnt+=can(i);
        }
    if (cnt==n) cout<<"YES";
    else cout<<"NO\n"<<cnt;
}