19. 최대 이분 매칭(Maximun Bipartite Matching)

  카페에 와서 샌드위치 하나와 커피 하나를 마신다고 가정해보자. 이 카페에서 선택할 수 있는 커피는 총 5가지가 있고, 샌드위치도 총 5가지가 있다. 이 경우, 내가 구매할 수 있는 커피와 샌드위치 구매 쌍은 총 25개가 된다는 점은 쉽게 직관적으로 알 수 있다. 이 때, 몇가지 조건을 추가해보기로 하자. 만약 커피1과 샌드위치 1,2를 먹으면 할인이 가능하고, 커피 2는 샌드위치 1,3을 먹으면 가능하다. 이와 같이 5종류의 커피 모두 특정 샌드위치와 먹게되면 할인이 가능한 이벤트를 진행중이다. 당신은 이벤트가 가능한 세트 하나를 선택하려고 한다. 그렇다면 당신이 선택할 수 있는 세트의 개수는 총 몇개인가?

  1. 최대 이분 매칭이란?

  이처럼 2개의 집합으로 니누어저 있는 정점을 연결 할 수 있는 최대 개수를 구하는 것이 최대 이분 매칭이다. 최대 이분 매칭에서 찾을 수 있는 이분 그래프는 아래와 같은 특징을 가지고 있다.

  - 정점이 두 집합으로 나뉜다.

  - 간선에 존재하는 두 정점은 서로 같은 집합 내에 존재하지 않는다.

  - 같은 집합 내에 있는 정점을 연결하는 간선은 존재하지 않는다.

  위와 같은 조건으로 형성된 간선을 '매칭(Matching)'이라고 한다. 아래는 이분 그래프의 경로이다.

  이분 그래프가 위와 같이 존재 한다고 했을 때, 가장 많은 매칭을 만들어 내는 것이 최대 이분 매칭의 목표이다. 매칭이 완성된 두 정점은 다른 매칭에 참여할 수 없게 된다. 위 그래프에서 우측에 있는 정점 집합을 숫자 순서대로 매칭해 나가는 방법으로 매칭 된 그래프를 구해보도록 하자. 설명을 쉽게 하기 위해서 좌측의 정점 집합을 A, 우측의 정점 집합을 B라고 하자.

  우선 A정점 가장 상위에 있는 1번 정점을 선택하고, 해당 정점에서 매칭이 되지 않은 B의 정점 하나를 구한다. B의 1번 정점이 매칭 되지 않았으니 A1과 B1을 매칭 시킨다.

  첫 번째 매칭이 완성되었으니 A2 정점으로 넘어가보자. 이 정점은 B2 하나와 연결되어 있으니 고민할 것 없이 바로 B3과 매칭 시켜준다.

  이번엔 A3 정점으로 넘어가자, 해당 정점과 연결된 B집합의 정점은 1,3으로 총 2개이다. 이 중 B1과 B3의 경우 이미 매칭이 완성되었다. 이런 경우엔 2차 매칭을 실시해야 한다. 우선 B1과 임시로 매칭을 실시해 A3와 B1을 연결한다. 이때, B1과 이미 매칭되어있던 A간선을 찾아야하고, 해당 정점은 A1이다. 이 정점이 다른 B의 정점과 매칭될 수 있는지 살펴 본다. 해당 정점의 경우 B2와 연결이 가능하다. 따라서, 아래와 같은 연결이 완성된다.

 

  앞서 소개한 순서대로 매칭을 시도하게 되면 자연스럽게 정점 A4는 정점 B4와 매칭이 완성된다. 이런 과정을 거쳐 최대 이분 매칭을 구할 수 있고, 위 이분 그래프의 최대 이분 매칭 수는 5가 된다.

2. 응용 문제

  앞서 말한 예제에 따라 처음에 언급한 문제를 한번 풀어보도록하자. 카페에는 N개의 커피 메뉴가 존재하고, 샌드위치는 M개가 존재한다고 가정하자. 각각의 커피마다 할인이 가능한 샌드위치가 존재한다. 예를들어 커피3과 샌드위치 1이나 2를 구매하게 된다면 세트 할인이 적용 된다. 

  해당 문제를 풀기 위해서 우선 필요한 입력값은 커피의 개수 N과 샌드위치의 개수 N이다. 그 아래에 i줄에서는 커피 i의 할을 메뉴 개수와 할인 샌드위치의 번호가 나온다.

Ex)

5 5

2 1 2

1 3

2 1 3

3 3 4 5

1 5

(쉬운 이해를 위해 위에 그린 이분 그래프와 동일하게 작성했다.)

  출력값은 당연히 해당 이분 그래프의 최대 이분 매칭 수 이다.

이 문제에 대한 코드는 아래와 같다.

import java.util.*;
 
public class Solution {
 
    public static ArrayList<Integer> mapping[];
    public static int answer;
    public static int[] Nmatching;
    public static int[] Mmatching;
    public static boolean[] visited;
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner sc = new Scanner(System.in);
        
        // Input
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        mapping = new ArrayList[N+1];
        
        for(int i=1; i<=N; i++){
            int size = sc.nextInt();
            mapping[i] = new ArrayList<Integer>();
            
            for(int j=0; j<size; j++){
                int tmp = sc.nextInt();
                mapping[i].add(tmp);
                
            }
        }
        
        // algo
        answer = 0;
        Nmatching = new int[N+1];
        Mmatching = new int[M+1];
        visited = new boolean[N+1];
        for(int i=1; i<=N; i++){
            if(matching(i)) answer++;
        }
        
        // output
        System.out.println(answer);
        
    }
 
    public static boolean matching(int i) {
 
        visited[i] = true;
        
        for(int k=0;k<mapping[i].size();k++){
            int j = mapping[i].get(k);
            if(Mmatching[j]==0||!visited[Mmatching[j]]&&matching(Mmatching[j]))  {
                Nmatching[i] = j;
                Mmatching[j] = i;
                return true;
            }
            
        }
        
        return false;
    }
 
}