이분 매칭 문제를 해결하는 증가 경로 알고리즘

//이분 매칭 문제를 해결하는 증가 경로 알고리즘
 
//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]에서 부터 시작해 증가 경로를 찾는다
            if(bMatch[b] == -1 || dfs(bMatch[b]))
            {
                //증가 경로 발견!! a와 b를 매치시킨다
                aMatch[a] = b;
                bMatch[b] = a;
                return true;
            }
    return false;
}
//aMatch, bMatch 배열을 계산하고, 최대 매칭의 크기를 반환한다
int bipartiteMatch()
{
    //처음에는 어떤 정점도 연결되어 있지 않다
    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;
}

 

 

 

 

 

 

이분 매칭 문제를 해결하는 증가 경로 알고리즘

이분 매칭이란 이분 그래프에서 최대 매칭을 찾는 문제 입니다.

이분 매칭은 Ford-Fulkerson Algorithm을 응용해 해결할 수 있습니다.

위의 그림처럼 검은색 정점들은 그룹 A, 녹색 정점들은 그룹 B라고 한다면, source는 그룹 A에 붙여주고, sink는 그룹 B에 붙여 주어 그래프 모델링을 할수 있습니다.

모든 간선의 용량은 1로 합니다.

두 그룹 간에 매칭이 1대1 로 이루어지는 점과, 모든 간선의 유량이 1인 이분 매칭 문제의 그래프 특성을 이용한다면, 알고리즘 자체는 다를게 없지만 구현이 간단한 코드를 짤수 있습니다.

 

 

 

 

 

 

시간복잡도

O(|V||E|)

(최대 유량이 V로 정해져 있고, 증가 경로를 한번 찾을때 마다 1씩 최대 유량이 증가하니 f는 |V|가 됩니다. 따라서 O(|V||E|)가 전체 시간 복잡도 입니다.)

 

 

 

 

 

 

프로그래밍 대회에서 배우는 알고리즘 문제해결전략2