알고리즘 스터디 39일차

1. 열혈강호

1) 문제

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

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

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

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

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

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

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int N, M;
vector<int> matchedEmployee;
vector<bool> jobVisited;
unordered_map<int, vector<int>> jobGraph;

bool dfs(int employee)
{
    for (int job : jobGraph[employee])
    {
        if (jobVisited[job]) continue;
        jobVisited[job] = true;

        // 현재 작업에 매칭된 사람이 없거나
        // 기존에 매칭된 사람이 다른 직업에 매칭 가능하면
        // 매칭
        if (matchedEmployee[job] == 0 || dfs(matchedEmployee[job]))
        {
            matchedEmployee[job] = employee;
            return true;
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int answer = 0;
    cin >> N >> M;

    matchedEmployee.resize(M+1);
    jobVisited.resize(M+1);

    for (int i=1; i<=N; i++)
    {
        int cnt;
        cin >> cnt;
        for (int j=0; j<cnt; j++)
        {
            int job;
            cin >> job;
            jobGraph[i].push_back(job);
        }
    }

    for (int i=1; i<=N; i++)
    {
        fill(jobVisited.begin(), jobVisited.end(), false);
        answer +=  dfs(i) ? 1 : 0;
    }

    cout << answer <<'\n';
    return 0;
}