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

#11378 열혈강호 4

난이도 : 플레 4

유형 : 이분 매칭

11378번: 열혈강호 4

▸ 문제

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

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 여기서 지난달에 벌점을 X점 받은 사람은 일을 최대 X+1개까지 할 수 있다.

예를 들어, 직원이 3명이고, 지난달에 1번 직원 민호가 벌점을 2점, 2번 직원 재필이가 벌점을 1점, 3번 직원 주현이가 벌점을 0점 받았다면, 1번 직원 민호는 일을 최대 3개, 2번 직원 재필이는 최대 2개, 3번 직원 주현이는 최대 1개까지 할 수 있다.

각 직원은 자신이 지난달에 받은 벌점을 알지 못하고, 직원이 받은 벌점의 합 K만을 알고 있다. 강호는 이런 사실을 이용해서 벌점을 적절히 나눠서 최대한 일을 많이 할 수 있게 하려고 한다.

예를 들어, 1번 직원이 1, 2, 3, 4, 5를 할 수 있고, 2, 3, 4번 직원이 1을 할 수 있고, 5번 직원이 1, 5를 할 수 있는 경우를 생각해보자.

지난 달에 전직원이 받은 벌점의 합 K가 0이라면, 할 수 있는 일의 최대 개수는 3개이다. 1번 직원이 2를 하고, 2번 직원이 1을, 5번 직원이 5를 하면 된다. 

벌점의 합 K가 2인 경우에, 1번 직원이 1점, 5번 직원이 1점을 받았다고 하면, 일을 최대 4개 할 수 있다. 1번 직원과 5번직원은 이제 일을 2개까지 할 수 있다. 1번 직원이 2와 3을, 5번 직원이 1과 5를 하면 총 4개의 일을 할 수 있다. 하지만, 강호가 벌점을 조작해 1번 직원이 2점을 받았다고 하면, 일은 최대 5개 할 수 있게 된다. 1번 직원은 일을 3개까지 할 수 있다. 따라서, 1번 직원이 2, 3, 4를 하고, 2번 직원이 1을, 5번 직원이 5를 하면 5개를 모두 할 수 있게 된다.

벌점의 합 K가 3인 경우에는, 1번 직원에게 벌점을 모두 몰아주면 일을 5개 할 수 있다. 1번 직원은 벌점이 3점이기 때문에, 일을 총 4개까지 할 수 있다. 따라서, 1, 2, 3, 4를 모두 1번직원이 하고, 5번 직원이 5를 하면 총 5가지 일을 할 수 있게 된다.

각각의 직원이 할 수 있는 일의 목록과 지난달 받은 벌점의 합 K가 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N)

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

▸ 출력

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

 

문제 풀이  

그리디한 방식을 고민했다. 처음에 무조건 많은 일을 할 수 있는 사람에게 몰아주는 식으로 코드를 작성했는데 20%에서 fail이 떴다. 왜냐하면 이렇게 작성하면 k를 다써버려서 무작정 많은 일을 할 수 있는 사람에게 일이 몰린다. 그래서 모두가 일을 배정받을 수 있음에도 최적 분배가 되지 않는다.

 

다음이 반례이다.

3 6 3
3 1 2 3
1 3
4 3 4 5 6

 

위의 방식으로 매칭을 하면 3번 직원에게 (3,4,5,6)일이 몰린다. 3번 직원에게 k를 몰아줬기 때문에 1번 직원이 (1) 1개만 할당받는다. 그래서 총 5개의 일을 구할 수 있다. 그러나 최적의 방식은 모두가 매칭을 하면 1번 직원은 (1, 2), 2번직원은 (3), 3번직원은(4, 5, 6)을 구하여 총 6개의 일을 구할 수 있다. 그래서 최적의 방식으로 다시 설계를 하면 모든 직원들에게 N개의 일을 골고루 분배한 후에 다시 K개의 일을 분배시켜준다. 

 

이분매칭

 

이분매칭에 대한 자세한 내용은 여기를 참고해주세요.

 

풀이 코드 

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());
		int k = 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++;
		}
		
		for(int i=1; i<=n; i++) {
			while(k > 0) {
				Arrays.fill(check, false);
				if(!dfs(i)) break;
				cnt++;
				k--;
			}
		}
		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;
	}
}