이분 매칭(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;
}