[C++] 11375번 열혈강호 - 이분 매칭

1. 문제

• 직원이 N명, 해야 할 일이 M개가 있다. 직원은 1~N번까지 번호가 매겨져 있고 일은 1~M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지를 구하여라

<입력>

• -1-   직원의 수 N, 일의 수 M \((1 \leq N, M \leq 1000)\)
• -2~N-   i번째 직원이 할 수 있는 일의 개수, 일의 번호

<출력>

• 강호내 회사에서 할 수 있는 최대 일의 개수를 출력

2. 재정의

• 직원과 일이 일대일 매칭일 때 할 수 있는 일의 최대 개수를 구하여라.

3. 해결 방법

• sour = 0, sink = N+M+1
• 0 -> (1~N)번 연결하기
• i번 직원과 할 수 있는 일의 번호가 j라고 하면 i와 N+j를 연결하기
• N+1 ~ N+M -> N+M+1 연결하기
• 최대 유량 알고리즘을 수행하여 최대 유량을 구하기

4. 실수한 점, 개선할 점

• 맨 처음에는 포인터를 이용해서 그래프를 표현했는데 포인터로 역탐색을 함으로써 시간 초과가 났다.
• 그래서 아예 배열을 크게 잡아서 했었는데 이 경우에도 소스코드가 통과는 했지만 1000ms를 넘어서 매우 느린 알고리즘임을 보였다.
• 이분 매칭은 dfs를 이용하면 시간 복잡도를 더 줄일 수 있다고 한다. 축사 배정 문제를 풀 때 dfs를 사용해서 풀어보자.

 

<코드>

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

const int INF = 987654321;
const int MAX_N = 2002;

//직원의 명수 N, 해야할 일 M
int N, M;
//sour, sink, 최대 유량
int sour, sink, total_flow;
//최대 유량 알고리즘을 적용할 그래프
vector<int> Edge[MAX_N];
//용량, 유량, 최대유량
int capacity[MAX_N][MAX_N], flow[MAX_N][MAX_N];
//최대 유량 알고리즘용 부모
int parent[MAX_N];

//간선 생성하기
void AddLine(int from, int to, int c) {
    capacity[from][to] = c;
    
    Edge[from].push_back(to);
    Edge[to].push_back(from);
}

void input() {
    cin >> N >> M;
    
    for(int i=1; i<=N; i++) {
        //0번과 직원을 연결하기
        AddLine(0, i, 1);
        
        int NumWork;
        
        cin >> NumWork;
        
        //직원과, 직원이 할 수 있는 일을 연결하기
        for(int j=1; j<=NumWork; j++) {
            int work;
            
            cin >> work;
            
            AddLine(i, N+work, 1);
        }
    }
    
    //작업과 N+M+1번을 연결하기
    for(int i=N+1; i<=N+M; i++)
        AddLine(i, N+M+1, 1);
    
    sour = 0, sink = N+M+1;
}

void MaximumFlow() {
    while(1) {
        memset(parent, -1, sizeof parent);
        
        //bfs
        queue<int> q;
        q.push(sour);
        
        while(!q.empty() && parent[sink] == -1) {
            int here = q.front(); q.pop();
            
            for(auto Next : Edge[here]) {
                if(capacity[here][Next] - flow[here][Next] > 0 && parent[Next] == -1) {
                    q.push(Next);
                    parent[Next] = here;
                }
            }
        }
        
        //sour에서 sink까지의 증가경로는 더 이상 없다.
        if(parent[sink] == -1)
            break;
        
        int amount = INF;
        for(int p = sink; p!=sour; p=parent[p])
            amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
        for(int p = sink; p!=sour; p=parent[p]) {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        
        total_flow += amount;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    //최대 유량 알고리즘
    MaximumFlow();
    
    cout << total_flow;
    
    return 0;
}

<주의> 이 코드는 구데기 코드임으로 이분 매칭 알고리즘을 공부하고자 온 사람이라면 다른 사람의 글을 보기를 추천합니다.

 

<이분 매칭 알고리즘>

https://yjg-lab.tistory.com/209

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

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.