Bipartite matching

1. Problem

- 이분 매칭 알고리즘을 이용하여 X 집단이 Y 집단을 선택하는 방법을 찾아보자.

- X 집단에 속하는 원소들이 Y 집단을 선택하는 조건이 주어질 때, 모든 조건을 만족하면서 X 집단의 모든 원소가 Y 집단의 원소를 선택하게 만든다.

- 이때 X 집단에 속하는 원소 a, b에 대해 a!=b라면 Y(a)!=Y(b)가 성립해야 한다.

 

2. Input

1) List<List<Character>> wishlist

- wishlist[i] = X 집단의 원소 i가 선택하고자 하는 문자가 담긴 list

 

3. Output

1) X 집단의 원소 x와 x가 선택한 Y 집단의 원소 y를 차례대로 출력

 

4. Example

// X = {1,2,3}, Y={A,B,C}
// 1번의 조건: A, B, C
// 2번의 조건: A
// 3번의 조건: C

// 1번 매칭: 가장 가까운 A를 선택한다
    {1,A}

// 2번 매칭: A를 원하지만 A는 이미 1번이 선택했다.
// 1번이 다른 것은 선택할 수 있는지 확인한다.
// 그 다음으로 가까운 B가 비어 있어서 B를 선택하고, A를 2번에게 양보한다.
    {1,B}, {2,A}

// 3번 매칭: B를 원하지만 B는 이미 1번이 선택했다.
// 1번이 다른 것은 선택할 수 있는지 확인한다.
// 그 다음으로 가까운 C가 비어 있어서 C를 선택하고, B를 3번에게 양보한다.
    {1,C}, {2,A}, {3,B}

// X 집단의 모든 원소를 방문했으므로 종료한다.
1 -> C
2 -> A
3 -> B

 

5. Code

// 클래스 변수
static int n = 3; // X = {1,2,3}, Y = {A, B, C}
static List<List<Character>> wishlist = new ArrayList<List<Character>>();
    // 1 -> {A, B, C}, 2 -> {A}, 3 -> {B}
static boolean[] occupied = new boolean[n+1]; // X 집단의 원소에게 선택됐다면 true
static int[] d = new int[n+1]; // Y 집단의 원소를 선택한 X 집단의 원소

// main()
for(int i=1 ; i<=n ; i++) {
    Arrays.fill(occupied, false);
    dfs(i);
}

static boolean dfs(int x) {
    for(int i=0 ; i<wishlist.get(x).size(); i++) {
        int y = wishlist.get(x).get(i)-'A'+1;
        if(occupied[y]) continue;
        occupied[y] = true;
        if(d[y]==0 || dfs(d[y])) {
            d[y] = x;
            return true;
        }
    }
    return false;
}

// main()
for(int i=1 ; i<=n ; i++)
    System.out.printf("%d -> %s\n", d[i], (char)('A'+i-1));
2 -> A
3 -> B
1 -> C

- 시간 복잡도: O(V+E)

- V는 노드의 개수, E는 간선의 개수