[알고리즘/그래프] 이분매칭(Bipartite Matching)

이분매칭(Bipartite Matching)이란?

---

이분 그래프(Bipartite Graph)에서 그래프의 최대 유량을 구하는 알고리즘으로 최대 매칭 수를 구할 수 있다. 최대 매칭수란, 어떤 정점이 다른 정점을 점유한 상태이며 각 정점은 한 개씩 점유가 가능한 경우를 말한다. 따라서 간선의 용량이 1인 경우에 해당한다.

• 즉 간선의 용량(capacity)이 1인 네트워크 플로우 문제이며, DFS(Depth-first-search)로 구현할 수 있다.
• 시간복잡도는 [] 으로, 에드몬드카프 알고리즘보다 효율적이다.

이미지 출처

이분 그래프(Bipartite Graph)란?

두개의 정점 그룹이 존재하고 간선의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프이다.

아래 이미지를 보면, U와 V 두개의 정점 그룹이 존재하고 양쪽의 정점이 각각 다른 그룹에 속한다. 이 때 모든 경로의 방향이 U에서 Y로 한 방향이며 간선의 용량(capacity)가 1인 그래프의 최대 유량(Max flow)를 구하는 것이 바로 이분 매칭이다.

이미지 출처

코드 구현

public class BipartiteMatching {
    public static final int MAX = 101; // 최대 노드 개수
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    static int[] d = new int[MAX]; // 특정 노드를 점유하고 있는 노드
    static boolean[] checked = new boolean[MAX]; // 특정 노드 처리 여부
    static int V = 3; // 노드의 개수

    static boolean dfs(int x) {
        // 연결된 모든 노드에 대해서 점유할 수 있는지 확인
        for(int i = 0; i < graph.get(x).size(); i++) {
            int t = graph.get(x).get(i);
            if(checked[t]) continue; // 이미 처리한 노드는 건너뜀
            checked[t] = true; // 처리 완료

            if(d[t] == 0 || dfs(d[t])) {
                // 비어있거나 점유 노드에 들어갈 공간이 있는 경우
                d[t] = x;
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // 인접행렬 초기화
        for(int i = 0; i < MAX; i++) {
            graph.add(new ArrayList<Integer>());
        }

        graph.get(1).add(1);
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(2).add(1);
        graph.get(3).add(2);

        int count = 0; // 매칭 개수

        for(int i = 1; i <= V; i++) {
            Arrays.fill(checked, false);
            if(dfs(i)) count++;
        }
        System.out.println("매칭 개수: " + count);

        // 매칭 정보 출력
        for(int i = 1; i < MAX; i++) {
            if(d[i] != 0) {
                System.out.println(d[i] + " -> " + i);
            }
        }
    }
}