[C++] 2188번 축사 배정 - 이분 매칭

1. 문제

• 소가 자신이 희망하는 몇 개의 축사에만 들어가고자 할 때 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1~M번으로 매겨져 있다.

<입력>

• -1-   소의 수 N, 축사의 수 M \((1 \leq N, M \leq 200)\)
• -2~N-   각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 \(S_{i}(0 \leq S_{i} \leq M)\).
• \(S_{i}\)개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.

<출력>

• -1- 축사에 들어갈 수 있는 소의 최댓값을 출력하라

2. 재정의

• 이분 매칭 최대 수를 구하시오.

3. 해결 방법

• 이분 매칭 알고리즘(dfs)를 이용하여 해결한다.

4. 실수한 점, 개선할 점

• 이미 확인한 정점을 제거할 때 done[Node]가 아닌 done[Next]를 확인하여야 한다. Next를 한 번 더 순환하면 되지 않는다는 것을 의미하기 때문이다.

 

<코드>

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

using namespace std;

const int MAX_VERTEX = 201;

//소의 수 N, 축사의 수 M
int N, M;
//정점 Vertex
vector<int> Vertex[MAX_VERTEX];
//Vertex가 점유하고 있는 정점
int Occupy[MAX_VERTEX];
//처리 여부
bool done[MAX_VERTEX];
//최대 유량
int total_flow;

void input() {
    cin >> N >> M;
    
    for(int i=1; i<=N; i++) {
        int cnt;
        cin >> cnt;
        
        for(int j=1; j<=cnt; j++) {
            int loveBarn;
            cin >> loveBarn;
            
            Vertex[i].push_back(loveBarn);
        }
    }
}

bool dfs(int Node) {
    //연결된 모든 정점에 대해 들어갈 수 있는지 시도
    for(int i=0; i<Vertex[Node].size(); i++) {
        int Next = Vertex[Node][i];
        //이미 처리한 정점은 고려하지 않음
        if(done[Next])
            continue;
        done[Next] = true;
        //비어있거나 점유 정점에 더 드어갈 공간이 있는 경우
        if(!Occupy[Next] || dfs(Occupy[Next])) {
            Occupy[Next] = Node;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    for(int i=1; i<=N; i++) {
        memset(done, false, sizeof done);
        if(dfs(i))
            total_flow++;
    }
    
    cout << total_flow;
    
    return 0;
}

 

<이분 매칭 알고리즘(dfs)>

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

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

 

 

 

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