[2188번] 축사 배정

문제 출처 :

https://www.acmicpc.net/problem/2188

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭(Bipartite Matching)

이분 매칭에 대한 개념을 이용한다면 쉽게 풀 수 있는 문제이다.

이분 매칭에 대한 개념 및 내용은 알고리즘 게시판에서 확인 할 수 있다.

주소 :: http://programbasic.tistory.com/499

이 코드에 대해 간단히 이야기 해보자면,

int main()부분부터 보자.

여기서 adj[i][val]의 의미는, 

A가 소고, B가 축사이며, adj[i][j]는 i번째 소가 b축사를 선호하면 1이라고 표시 한다는 의미이다.

그다음 bipartiteMatch()부분을 보자.

aMatch :: 소의 수만큼 -1로 초기화 해준다. 

bMatch :: 축사의 수만큼 -1로 초기화 해준다. 

이 초기화의 의미는 어떤 소와 어떤 축사가 아직 연결되어 있지 않다는 의미이다.

dfs(start) 부분을 통해 이제 dfs로 가보자.

visited[a] :: dfs를 통한 방문이기에 이전에 a부분을 방문한 적있는지 체크를 해 두어야 한다.

if(adj[a][b]) :: a번째 소가 b번째 축사를 원하고 있는가? 

원하지 않고 있다면 다음 축사를 보도록 하고(for문을 통해)

원하고 있다면 if(bMatch[b] == -1 || dfs(bMatch[b]) :: 축사 b가 이미 다른 소와 매칭되어있는가?

< 참고로 if문에서 bMatch[b] == -1이 true라면 오른쪽 dfs부분은 보지 않고 if(1)로 프로그램이 처리해버린다.

bMatch[b] == -1이 false일때만 dfs(bMatch[b])를 본다. >

매칭되어 있지 않다면

a번째 소가 b번째 축사를 가르키도록,

b번째 축사가 a번째 소를 가르키도록 서로 이어준다.

매칭되어 있다면

dfs(bMatch[b]) :: b번째 축사를 보고 있는 a번째 소를 다시 보자는 의미이다.

다시 dfs 처음으로 와서 a번째 소가 그다음번째 것을 보고 매칭할 수 있다면 

a번째 소는 새로운 축사랑 매칭을 하고 return true를 한다.

그리고 다시 b번째 소로 돌아와서 b번째 소는 이전에 가리키고 있던 축사와 매칭을 하는방식이다. 

이렇게 계속 찾다보면,

결국 소와 축사의 연결이 최댓값이 되도록 구할 수 있게 된다.

소스 코드 : 

#include <iostream>
#include <vector>
 
using namespace std;
 
#define MAX_N 201
#define MAX_M 201
 
// A와 B의 정점의 개수
int n, m;
 
// adj[i][j] = Ai와 Bj가 연결되어 있는가?
bool adj[MAX_N][MAX_M];
 
// 각 정점에 매칭된 상대 정점의 번호를 지정한다.
vector<int> aMatch, bMatch;
 
// dfs()의 방문 여부
vector<bool> visited;
 
// A의 정점인 a에서 B의 매칭되지 않은 정점으로 가는 경로를 찾는다.
bool dfs(int a)
{
    if (visited[a])
        return false;
 
    visited[a] = true;
 
    for (int b = 0; b < m; b++)
    {
        if (adj[a][b])
        {
            // b가 매칭되어 있지 않다면 bMatch[b]에서부터 시작해 증가 경로를 찾는다.
            // 매칭되어 있다면 dfs에서 매칭되어있는 A정점이 다른 곳을 매칭 할 수 있는지 본다.
            if (bMatch[b] == -1 || dfs(bMatch[b]))
            {
                // 증가 경로를 발견하였을 때, a와 b를 매치시킨다.(이어준다.)
                aMatch[a] = b;
                bMatch[b] = a;
 
                return true;
            }
        }
    }
 
    return false;
}
 
// aMatch, bMatch 배열을 계산하고 최대 매칭 크기를 반환한다.
int bipartiteMatch()
{
    // -1로 초기화 (어떤 정점과도 연결되어 있지 않다는 의미)
    aMatch = vector<int>(n, -1);
    bMatch = vector<int>(m, -1);
 
    int size = 0;
 
    for (int start = 0; start < n; start++)
    {
        visited = vector<bool>(n, false);
 
        // 깊이 우선 탐색을 이용해 start에서 시작하는 증가 경로를 찾는다.
        if (dfs(start))
            size++;
    }
 
    return size;
}
 
int main()
{
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        // i번째 소가 선호하는 축사의 수
        int cnt;
 
        cin >> cnt;
 
        for (int j = 0; j < cnt; j++)
        {
            // 축사 번호
            int val;
            cin >> val;
            val--;
 
            adj[i][val] = 1;
        }
    }
 
    cout << bipartiteMatch();
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>