[BOJ 17481 // C++] 최애 정하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17481번 문제인 최애 정하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/17481

17481번: 최애 정하기

 

이 문제는 N명의 "친구들"을 한 묶음으로, 문제에서 주어지는 각 걸그룹 멤버 M명을 한 묶음으로 생각해 이분매칭(maximum bipartite matching) 문제로 풀 수 있다.

 

각 걸그룹 멤버의 이름이 문자열로 주어지므로, map을 이용해 서로 다른 자연수로 대응시켜주고 이분매칭을 진행하면 간단히 풀 수 있다.

 

아래는 제출한 소스코드이다.

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

map<string, int> strtoidx;

vector<int> G[1001];
int visited[1001];
int matching[1001];

int dfs(int current) {
    if (visited[current]) return 0;
    visited[current] = 1;
    for (auto node : G[current]) {
        if (matching[node] == 0) {
            matching[node] = current;
            return 1;
        }
        if (dfs(matching[node])) {
            matching[node] = current;
            return 1;
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;
    for (int i = 1;i <= M;i++) {
        string s; cin >> s;
        strtoidx.insert({ s, i });
    }

    for (int i = 1;i <= N;i++) {
        int K; cin >> K;
        for (int k = 0;k < K;k++) {
            string s; cin >> s;
            G[i].push_back(strtoidx[s]);
        }
    }

    int ans = 0;
    for (int i = 1;i <= N;i++) {
        memset(visited, 0, sizeof(visited));
        ans += dfs(i);
    }

    if (ans == N) cout << "YES";
    else cout << "NO" << '\n' << ans;
}