BOJ 17481 - 최애 정하기 링크
(2023.05.01 기준 P4)

문제

N명의 친구들마다 좋아하는 걸그룹 멤버들이 있다. 최애 멤버를 1명씩 정하려고 하는데, 친구들끼리 겹치지 않게끔 정하려고 한다. 이 때, 최대한 겹치지 않게 친구들 전체가 좋아할 수 있는 최대 멤버 수 출력

알고리즘

이분 매칭

풀이

N명의 친구들과 M명의 걸그룹 멤버가 주어진다. 이 때, 걸그룹 멤버는 이름으로 주어진다. 그러니 해시 맵을 이용하여 번호를 배정하자.

각 친구마다 좋아하는 걸그룹 멤버들이 주어지면 이를 그대로 그래프에 간선으로 추가하고, 그대로 이분 매칭 돌려주면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int matched[1000];
bool visited[1000];
vector<int> graph[1000];

// 이분 매칭
bool dfs(int i){
    for (int j: graph[i]){
        if (visited[j]) continue; // 이미 고려한 걸그룹 멤버면 넘어가자.
        visited[j] = true;

        // 걸그룹 멤버와 매칭된 친구가 없거나 그 친구의 매칭을 다시 시도하여 성공할 경우
        if (matched[j] == -1 || dfs(matched[j])){
            matched[j] = i; // 매칭 성공
            return true;
        }
    }

    // 모두 실패했다면 매칭 실패
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    // 걸그룹 멤버마다 번호를 0번부터 순서대로 배정
    string name;
    map<string, int> members;
    for (int i = 0; i < M; i++) cin >> name, members[name] = i;

    // 좋아하는 멤버로 향하는 간선을 그래프에 추가
    for (int i = 0, K; i < N; i++){
        cin >> K;
        while (K--) cin >> name, graph[i].push_back(members[name]);
    }

    fill(matched, matched + M, -1); // 걸그룹 멤버별 매칭 상황
    int result = 0;
    for (int i = 0; i < N; i++){
        fill(visited, visited + M, false);
        if (dfs(i)) result++;
    }

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

• Python

import sys; input = sys.stdin.readline

# 이분 매칭
def dfs(i):
    for j in graph[i]:
        if visited[j]: # 이미 고려한 걸그룹 멤버면 넘어가자.
            continue
        visited[j] = True

        # 걸그룹 멤버와 매칭된 친구가 없거나 그 친구의 매칭을 다시 시도하여 성공할 경우
        if matched[j] == -1 or dfs(matched[j]):
            matched[j] = i # 매칭 성공
            return True

    # 모두 실패했다면 매칭 실패
    return False

N, M = map(int, input().split())

# 걸그룹 멤버마다 번호를 0번부터 순서대로 배정
members = dict()
for i in range(M):
    name = input().strip()
    members[name] = i

# 좋아하는 멤버로 향하는 간선을 그래프에 추가
graph = [[] for _ in range(N)]
for i in range(N):
    K, *likes = input().split()
    for like in likes:
        graph[i].append(members[like])

matched = [-1] * M # 걸그룹 멤버별 매칭 상황
result = 0
for i in range(N):
    visited = [False] * M
    if dfs(i):
        result += 1

print('YES') if result == N else print('NO\n%d' % result)