[BOJ] 백준 11375번 열혈강호 (Java)

#11375 열혈강호

난이도 : 플레 4

유형 : 이분 매칭 

11375번: 열혈강호

▸ 문제

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

▸ 출력

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

 

문제 풀이  

네트워크 플로우와 연계되는 개념인 이분 매칭(Bipartite Matching) 알고리즘 문제이다. 이분 매칭은 이분 그래프에서 최대 매칭을 찾는 문제를 간단하게 이분 매칭이라고 부른다.

• 그룹 A(직원)와 그룹 B(일)를 주어진 대로 연결하고 용량을 1로 하면 해당 그래프의 최대 유량을 구한 뒤 유량이 흐르는 간선을 모으면 최대 매칭이 된다.

 

시뮬레이션

이분 매칭 구현은 포드-폴커슨 알고리즘처럼 증가 경로를 찾은 뒤 유량을 보내는 것을 반복해주면 된다. 문제에서 주어진 예제를 통해 시뮬레이션을 돌려보자.

 

1번 직원 일 배정하기

• 1번 직원은 (a, b)에 매칭이 가능하므로, 일단 a랑 매칭한다.

1번 직원 매칭하기

 

2번 직원 일 배정하기

• 2번 직원은 (a)에 매칭이 가능하다.
• 그런데 이미 a는 1번 직원이랑 매칭되어 있으므로, 1번에게 다른 과제 부여가 가능한지 확인한다.
• 결과 1번 직원 b에 재매칭하고, 2번을 a와 매칭한다.

2번 직원 매칭하기

 

3번 직원 일 배정하기

• 3번 직원은 (b, c)에 매칭이 가능하다.
• 3번 직원을 b에 매칭하려면, 1번이 a로 돌아가야 하고, 2번이 다른 일을 점유해야하는데 불가능하다.
• 결과 3번 직원을 c에 매칭한다.

3번 직원 일 배정하기

 

4번 직원 일 배정하기

• 4번 직원은 (c, d, e)에 매칭이 가능하다.
• 4번을 c에 매칭하려면 3번을 a로 매칭시켜야하는데, 위에서 했다시피 불가능하다.
• 결과 4번 직원은 d에 매칭한다.

4번 직원 일 배정하기

 

5번 직원 일 배정하기

• 5번 직원은 (a)에 매칭이 가능하다.
• 그러나 이미 점유하고 있는 직원들이 있기 때문에 매칭이 불가능하다.

 

그 결과 총 매칭이 된 갯수는 총 4개이다.

 

 

DFS 탐색으로 직원-일 매칭 로직 만들기

이분매칭의 동작 원리만 안다면 구현은 간단하다. 1~n번 직원을 순차적으로 탐색하여, 일(task)가 비어있거나 이미 점유하고 있는 직원이 다른 일을 맡을 수 있는 경우에만 현재 직원(here)을 nxt 일에 배정해주면 된다.

public static void main(String[] args) throws IOException{
    int cnt = 0;
    for(int i=1; i<=n; i++) {
        Arrays.fill(check, false);
        if(dfs(i)) cnt++; // 매칭되었으면 cnt++
    }
}

static boolean dfs(int here) {
	for(int nxt : list[here]) {
		
		if(check[nxt]) continue;
		
		check[nxt] = true;
		
		if(task[nxt] == 0  || dfs(task[nxt])) {
			task[nxt] = here;
			return true;
		}
	}
	
	return false;
}

 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	static List<Integer>[] list;
	static int[] task;
	static boolean[] check;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			list[i] = new ArrayList<>();
		}
		
		task = new int[m+1];
		check = new boolean[m+1];
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			int nn = Integer.parseInt(st.nextToken());
			for(int j=0; j<nn; j++) {
				list[i].add(Integer.parseInt(st.nextToken()));
			}
		}
		
		int cnt = 0;
		for(int i=1; i<=n; i++) {
			Arrays.fill(check, false);
			if(dfs(i)) cnt++; 
		}
		
		System.out.println(cnt);
		
	}
	
	static boolean dfs(int here) {
		for(int nxt : list[here]) {
			
			if(check[nxt]) continue;
			
			check[nxt] = true;
			
			if(task[nxt] == 0  || dfs(task[nxt])) {
				task[nxt] = here;
				return true;
			}
		}
		
		return false;
	}
}