(백준 c++)11375 열혈강호

문제

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

 

 

이분매칭이라는 새로운 알고리즘 방법을 배웠다.

나동빈님의 블로그에 자세한 설명이 있으니 참고..!

blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240613074&redirect=Dlog&widgetTypeCall=true&directAccess=false

29. 이분 매칭(Bipartite Matching)

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> worker(1001);
vector<int> available(1001, 0);
vector<bool> check(1001, false);

bool dfs(int number){
    for(int i = 0; i < worker[number].size(); i++){
        int work = worker[number][i];

        //일이 이미 매칭된 경우 continue
        if(check[work]){
            continue;
        }

        check[work] = true;
        
        //일이 아무도 매칭되어있지 않거나, 직원이 현재 일 외에 다른 일을 할 수 있는 경우 찾기
        if(available[work] == 0 || dfs(available[work])){
            available[work] = number;
            return true;
        }
    }
    return false;
}

int main(void){
    int ans = 0, N, M;

    cin >> N >> M;
    
    for(int i = 1; i <= N; i++){
        int num;

        cin >> num;

        for(int j = 0; j < num; j++){
            int tmp;
            
            cin >> tmp;
            worker[i].push_back(tmp);
        }
    }

    //이분매칭
    for(int i = 1;  i <= N; i++){
        //최대한 모든 일을 해야하기 때문에 false로 바꿔주어 최대로 매칭하기
        fill(check.begin(), check.end(), false);
        if(dfs(i)){
            ans++;
        }
    }
    
    cout << ans;

    return 0;
}