[java] 이분 매칭 알고리즘

04 Dec 2023

java

이분 매칭 알고리즘은 그래프 이론에서 사용되는 알고리즘 중 하나로, 어떤 집합과 다른 집합 사이의 매칭을 구하는 알고리즘입니다. 이 알고리즘은 간단하면서도 효율적인 방법으로 최대 매칭 문제를 해결할 수 있습니다.

알고리즘 개요

초기 매칭을 모두 제거한다.
매칭이 될 수 있는 모든 간선들을 하나씩 검사한다.
만약 해당 간선에 연결된 정점이 아직 매칭되지 않았다면, 해당 간선을 매칭한다.
만약 해당 간선에 연결된 정점이 이미 매칭되어 있다면, 다른 경로가 존재할 수 있는지 확인한다.
다른 경로가 존재한다면, 현재 매칭된 간선을 제거하고 해당 간선으로 매칭한다.
모든 간선에 대해 이 과정을 반복한다.
반복이 끝나면 최대 매칭이 완성된다.

예시 코드

import java.util.Arrays;

public class BipartiteMatching {

    private static int[] match; // 각 정점에 매칭된 상대 정점
    private static boolean[] visited; // DFS 방문 여부 체크
    private static boolean[][] graph; // 그래프의 연결 관계 정보

    private static int n; // 왼쪽 그룹의 정점 개수
    private static int m; // 오른쪽 그룹의 정점 개수

    public static int getMaxMatching() {
        match = new int[m];
        Arrays.fill(match, -1); // 초기 매칭 없음

        int count = 0; // 최대 매칭 개수

        for (int i = 0; i < n; i++) {
            visited = new boolean[n];
            if (dfs(i)) {
                count++; // 매칭 성공 시 개수 증가
            }
        }

        return count;
    }

    private static boolean dfs(int u) {
        visited[u] = true;

        for (int v = 0; v < m; v++) {
            if (graph[u][v]) {
                if (match[v] == -1 || !visited[match[v]] &&
                        dfs(match[v])) {
                    match[v] = u;
                    return true;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        n = 4;
        m = 4;
        graph = new boolean[][]{
                {true, true, false, false},
                {true, false, true, false},
                {false, true, false, true},
                {false, false, true, false}
        };

        int maxMatching = getMaxMatching();
        System.out.println("최대 매칭 개수: " + maxMatching);
    }
}

알고리즘 개요

예시 코드

참고 자료