이분 매칭 알고리즘 ( JAVA),열혈강호1,2,3 문제

이분 매칭 알고리즘이란 용량이 1인 이분 그래프에서 최대로 매칭 할수 있는 수를 구하는 알고리즘이다.

 

기본적으로 DFS알고리즘을 사용한다.

 

알고리즘 매커니즘

기본 적으로 1~N 노드 까지 DFS 탐색을한다. 이때 각각의 노드마다 Dfs탐색을 한다.

1. 현재 here 노드에서 연결된 there 노드가 방문하지않았으면 there은 here과 이어젔다고 표시한후 true를 반환

2. 만약 there이 누군가와 연결되었다면 there과 연결한 간선을 다시 Dfs탐색하여 다른것과 매칭 할수 있는지 탐색 만약 할수 있다면 here과 there을 이어준다. 그리고 true를 반환한다.

3. 위에 1, 2 번으로 이을수 없다면 false를 반환한다.

4. 1 2 3 을 1~N 번 노드 까지 반복한다. 그때마다 Dfs를 돌리기위해서 visit을 초기화 시켜준다.

 

소스코드

package 개인공부;
 
import java.util.ArrayList;
import java.util.Arrays;
 
public class 이분매칭 {
    // 네트워크 유량 문제에서 모든 간선의 용량이 1이고 이분그래프가 그려질경우 최대 매칭 알고리즘을 DFS로 짤 수있다
    static final int MAX_N = 1001;
    static int n, m;
    static boolean visit[] = new boolean[MAX_N];
    static int b[] = new int[MAX_N];
    static ArrayList<Integer> ver[] = new ArrayList[MAX_N];
 
    static int bmath() {
        int ret = 0;
 
        for (int i = 1; i <= n; i++) {
 
            // 방문 배열 초기화
            Arrays.fill(visit, false);
 
            if (dfs(i)) {
                ret++;
            }
        }
 
        return ret;
    }
 
    public static boolean dfs(int here) {
        if (visit[here])
            return false;
        
        visit[here] = true;
 
        for (int there : ver[here]) {
 
            if (b[there] == 0 || dfs(b[there])) {
                b[there] = here;
                return true;
            }
        }
 
        return false;
    }
}
 

 

예제문제들을 푸는 접근방법

 

1. 열혈강호

기본적인 이분매칭 알고리즘을 적용

2. 열혈강호2

기본적인 이분매칭 알고리즘을 적용할때 하나의 사원이 최대 2번 매칭할수있다고하니
Dfs알고리즘을 두번시행하는 것으로 문제를 풀수 있다.

3.열혈강호3

기본적으로 이분매칭알고리즘이 끝낫을때 1~n번까지 Dfs를 다시한번 돌린다. 이대 Dfs가 true라면 cnt를 하나늘려주고 cnt == K가 되는순간에는 그만 return 한다.

이렇게 해도 되는 이유는 n번째 노드의 연결 가능성을 고려할 때 n과 연결된 간선들중에 방문을 햇다고하더라도
Dfs가 다시 그간선을 다른곳에 이을수 있는지 확인한다. 이말은 n번째 노드를 y번째 노드에 이을 수 있는지 검사할때 이미 연결된 간선들을 최대한 정렬해서 이을 수 있는지 판단한다. 다라서 1~n번 노드들을 돌면서 이분매칭가능성을 고려해서 된다고햇을때 K값을 하나 줄일수 있다.

기본 이분매칭수 + 최대 K 인데  이때 최대 K까지 갈수있는지를 조사하면되는것이다 1~N번노드까지