BOJ 11375 : 열혈강호 [C++]

 

11375번: 열혈강호

 

3일 전에 틀리고 '블로그에 옮기면서 다시 한번 봐야지' 했는데 이제야 쓴다.

분명 이분 매칭 문제를 푼 기억이 있는데, 문제를 보고 이분 매칭을 떠올리지 못했다.

 

 

이분 매칭을 잘 설명한 글

 

[알고리즘] 이분 매칭 알고리즘 (Bipartite Matching)

 

이분 매칭(Bipartite Matching)

 

bool dfs(int worker) {
    if (visited[worker]) {
        return false;
    }
    
    visited[worker] = true;
    
    for (int job : graph[worker]) {
        if (assigned_to[job] == 0 || dfs(assigned_to[job])) {
            assigned_to[job] = worker;
            return true;
        }
    }

    return false;
}

 

이미 방문했던 정점(직원)이라면 false return

 

내가(현재 dfs를 진행하는 직원이) 할 수 있는 일의 목록을 순회하며 일을 하나씩 살펴본다.

 

1. 아직 어떤 직원에게도 할당되지 않은 경우

2. 이미 하기로 한 직원(B)이 있지만,  해당 직원(B)이 다른 일을 맡을 수 있어 내가 해도 되는 경우

두 경우에 해당한다면 일을 나에게 할당하고 true를 return

 

어떤 일도 내가 맡을 수 없다면(어떤 일도 나에게 할당될 수 없다면) false return

 

 

 

코드

#include <iostream>
#include <vector>
#include <cstring>

int N, M;
std::vector<int> graph[1001];
bool visited[1001];
int assigned_to[1001];

bool dfs(int worker) {
    if (visited[worker]) {
        return false;
    }
    
    visited[worker] = true;
    
    for (int job : graph[worker]) {
        if (assigned_to[job] == 0 || dfs(assigned_to[job])) {
            assigned_to[job] = worker;
            return true;
        }
    }

    return false;
}

int main() {
    std::cin >> N >> M;

    int jobs, job;
    for (int i = 1; i < N + 1; i++) {
        std::cin >> jobs;
        for (int j = 0; j < jobs; j++) {
            std::cin >> job;
            graph[i].push_back(job);
        }
    }

    int answer = 0;
    for (int i = 1; i < N + 1; i++) {
        std::memset(visited, false, sizeof(visited));
        if (dfs(i)) {
            answer++;
        }
    }

    std::cout << answer << "\n";

    return 0;
}