이분 매칭(Bipartite Matching)

[WonYong-Jang]

이분매칭

• 네트워크 플로우 개념중에서 이분 그래프에서의 최대 유량을 구하는 경우를 이분 매칭

출처 : https://jason9319.tistory.com/149

DFS 를 이용한 이분매칭 O(V*E)

열혈 강호 11375

public class baek11375 {

    static int N, M, result;
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
    static int[] visit = new int[1005];
    static int[] match = new int[1005];
    public static void main(String[] args) throws IOException {

        int result = bmatch();
        System.out.println(result);
    }
    public static int bmatch()
    {
        int ret = 0;
        for(int i=1; i<= N; i++) // 모든 직원들에 대해서 매칭 시도 
        {
            for(int j=1; j<= N; j++) visit[j] = 0;
            if(dfs(i) == 1) ret++; // 직원과 일이 매칭 된다면 카운트 
        }
        return ret;
    }
    public static int dfs(int cur)
    {
        if(visit[cur] == 1) return 0; // 방문한 직원 매칭 불가 
        visit[cur] = 1;

        for(int next : adj.get(cur))
        {
            // 매칭한 적이 없거나 매칭 되어 있다면 매칭 된 직원에게 되돌아 가서 다른 일이 가능한지 확인 작업 
            if(match[next] == 0 || dfs(match[next]) == 1)
            {
                match[next] = cur; // 매칭이 된다면 1 리턴 
                return 1;
            }
        }

        return 0;
    }
}

열혈강호 2

• 한사람당 최대 2가지 일 매칭 가능 각 사람에 대해 이분 매칭 2번 돌려주면 끝

  public static int bmatch()
  {
  int ret =0;
  
  for(int i=1; i<= N; i++)
  {
      for(int j=1; j<= 2; j++)
      {
          for(int k=1; k<= N; k++) visit[k] = 0;
          if(dfs(i) == 1) ret++;
      }
  
  }
  return ret;
  }

열혈강호 3

• N명 중 K명이 최대 2개 일을 할수 있는데 , K명은 누구든 상관 없음 => N+K 개로 열혈강호 2처럼 돌린다면 반례가 생김 ex) N = 5, K =3 일때 최대 2개 일할수 있는 사람이 3명이 되야 하는데 4명이 생길수 있음 / 1,2,3,4 직원이 2개씩 일하고 5 직원이 1개 일하는 경우 발생 / ( 총 유량 8 )

==> 첫번 째 정점 그룹 P, 두번 째 정점 그룹 Q로 나누고 일단 맨 처음은 P그룹의 N개 정점들에 대해서만 최대 매칭을 구함 그 다음, Q 그룹의 N개의 정점들에 대해서만 최대 매칭을 구하는대 이때 K개 발생하면 중단 ==> 성립 이유는 Q그룹에서 매칭을 새로 찾다가 원래 매칭이 있던 P 그룹의 정점이 매칭이 없어지는 일은 발생하지 않음

public static int bmatch()
{
    int ret = 0, count = 0;

    for(int i=1; i<= N; i++)
    {
        for(int j=1; j<= N; j++) visit[j] = 0;
        if(dfs(i) == 1) ret++;
    }

    for(int i=1; i<= N; i++)
    {
        for(int j=1; j<= N; j++) visit[j] = 0;
        if(dfs(i) == 1) {
            ret++;
            count++;
        }
        if(count == K) break;
    }
    return ret;
}