이분 매칭 (Bipartite Matching)

두 그룹으로 구분된 정점과, 서로 다른 그룹의 정점을 연결하는 간선들로 이루어진 그래프를 이분 그래프(Bipartite Graph)라고 합니다. 그룹 A에 속하는 정점 Ai와 그룹 B에 속하는 정점 Bj를 연결하는 간선 (Ai, Bj)을 선택하는 것을 매칭이라고 합니다. 이때 모든 정점은 단 하나의 매칭에만 속해야 합니다. 즉, 선택한 모든 매칭은 같은 정점이 중복되어서는 안 됩니다. 최대 매칭이란 이분그래프에서 선택할 수 있는 매칭의 최대 개수를 의미합니다. 이러한 문제를 이분매칭(Bipartite Matching) 혹은 최대이분매칭(Maximum Bipartite Matching)이라고 합니다.

위는 이분그래프의 예제입니다. 오른쪽 그래프에서 파란색으로 칠해진 것보다 많은 간선을 주어진 조건에 맞도록 선택할 수 없습니다. 따라서 오른쪽 그래프의 최대 이분 매칭의 개수는 3입니다.

이러한 최대 매칭의 개수를 어떻게 구할 수 있을까요? 이분매칭 문제는 앞서 다룬 최대 유량 문제로 변형해서 접근할 수 있습니다. 아래와 같은 유량그래프를 생각해봅시다.

앞서 다룬 이분 그래프에서 위와 같이 가상의 Source와 Sink를 만들고, Source에서 그룹 A의 모든 정점으로 향하는 간선을, 그룹 B의 모든 정점에서 Sink로 향하는 간선을 추가해봅시다. 그리고 모든 간선의 capacity를 1로 설정해 봅시다. 이때 A그룹의 임의의 노드 Ai로 들어오는 최대 유량이 1이기 때문에 Ai에서 출발하는 간선 중 단 하나의 간선을 통해서만 1의 유량이 빠져나갈 수 있습니다. 반대로 그룹 B의 임의의 노드 Bj에서 sink로 빠져나갈 수 있는 최대 유량이 1이기 때문에 Bj로 아무리 많은 간선이 들어오더라도 그중 하나의 간선을 통해 받은 1의 유량 외에는 의미가 없습니다.

이러한 제약을 통해 생각해보면, 이 네트워크는 최대한 많은 유량을 흘려보내기 위해 두 그룹 사이를 이어주는 간선(매칭)을 최대한 활용하는 방향으로 최적화를 진행하게 됩니다. 따라서 위 유량그래프의 최대유량은 앞서 다룬 이분 그래프에서의 최대 매칭과 같아집니다.

아래는 이분 그래프의 정보가 주어졌을 때 최대 매칭을 구하는 코드입니다. 이분 그래프에서 최대 유량은 A그룹의 정점의 수와 B그룹의 정점의 수 중 최솟값보다 작기 때문에 Ford-Fulkerson 알고리즘을 사용하더라도 O(VE)의 시간 복잡도를 보장할 수 있습니다.

입력	출력
첫 줄에 정점의 개수 V와 간선의 개수 E가 주어집니다. (1 ≤ V ≤ 1,000, 1 ≤ E ≤ 10,000) 두 번째 줄부터 E개의 줄에 걸쳐 V1, V2가 주어집니다. 이는 V1과 V2를 연결하는 간선이 존재한다는 의미입니다. (1 ≤ V1, V2 ≤ V) 입력되는 그래프는 V1집합과 V2집합으로 구분되는 이분 그래프임이 보장됩니다.	주어진 이분그래프의 최대매칭을 출력합니다.
Sample Input	Sample Output
8 7 1 5 1 6 2 5 2 6 2 8 3 7 4 7	3

import java.util.*;
import java.lang.*;

public class Main {
    static List<NetworkEdge>[] adj = new ArrayList[1002];
    static boolean chk[] = new boolean[1002];
    static int group[] = new int[1002];
    static int src, sink;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int v = sc.nextInt();
        int e = sc.nextInt();
        for (int i = 0; i <= v + 1; i++) {
            adj[i] = new ArrayList<NetworkEdge>();
        }

        src = 0;
        sink = v + 1;

        for (int i = 0; i < e; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            add_edge(v1, v2, 1);
            group[v1] = 1;
            group[v2] = 2;
        }

        for (int i = 1; i <= v; i++) {
            if (group[i] == 1) {
                add_edge(src, i, 1);
            }
            else if (group[i] == 2) {
                add_edge(i, sink, 1);
            }
        }

        int ans = 0, added_flow;
        while (0 < (added_flow = find_path(src, 101))) {
            ans += added_flow;
            for (int i = 0; i <= v + 1; i++) {
                chk[i] = false;
            }
        }

        System.out.println(ans);
    }

    public static void add_edge(int from, int to, int capacity) {
        adj[from].add(new NetworkEdge(to, capacity, 0, adj[to].size()));
        adj[to].add(new NetworkEdge(from, 0, 0, adj[from].size() - 1));
    }

    public static int find_path(int cur, int addible_flow) {
        if (cur == sink) return addible_flow;
        chk[cur] = true;

        for (int i = 0; i < adj[cur].size(); i++) {
            NetworkEdge edge = adj[cur].get(i);
            if (chk[edge.to] || edge.capacity - edge.flow == 0) continue;

            int added = find_path(edge.to, Math.min(addible_flow, edge.capacity - edge.flow));
            if (0 < added) {
                edge.flow += added;
                adj[edge.to].get(edge.residual_idx).flow -= added;
                return added;
            }
        }
        return 0;
    }

    static class NetworkEdge {
        int to, capacity, flow, residual_idx;

        NetworkEdge(){}

        NetworkEdge(int t, int c, int f, int ridx) {
            to = t;
            capacity = c;
            flow = f;
            residual_idx = ridx;
        }
    }
}