BOJ 백준 11378 열혈강호 4

문제 : https://www.acmicpc.net/problem/11378

[ 문제 요약 ]

• 직원 N 명, M 개의 일이 주어집니다.
• 벌점 X 점 받은 사람은 일을 최대 X + 1개까지 담당할 수 있습니다.
• 각 직원은 자신이 받은 벌점은 모르고, 직원이 받은 벌점의 합 K만을 알고 있습니다. 벌점을 각 사람에게 적절히 분배해 일을 최대로 하게 할 때, 할 수 있는 일의 최댓값을 출력합니다.

 

[ 테스트 케이스 설명 ]

5 5 1// 직원 수(1<=1,000), 일의 수(1<=1,000), 벌점의 합(1<=사람수)
5 1 2 3 4 5 // N개 줄에 i번 직원이 할 수 있는 일의 개수와 그 일의 번호가 주어짐
1 1
1 1
1 1
2 1 5
최대 가능한 일 : 4

 

 

[ 알고리즘 분류 ]

• 최대 유량
• 이분 매칭

 

[ 문제 해설 ]

 

이분 매칭 문제로, 확실한 것은 일을 많이 할 수 있는 직원이 많은 점수를 받아야 합니다.

 

그러나 단순히 이렇게 일이 많은 직원 순으로 벌점을 더 주면 반례가 생깁니다. 일을 적게 할 수 있는 직원이지만 유일하게 처리 가능한 일이 있을 때, 이 직원에게 벌점을 더 줘야 하기 때문입니다.

 

처음부터 벌점을 직원들에게 나눠 주는 게 아니라, 반대로 이분 매칭을 돌린 후 처리 가능한 일이 있는 직원에게만 벌점을 주는 방식으로 진행합니다.

 

먼저 각 직원을 순회하며 할 수 있는 일을 카운팅 합니다.

 

그 후 추가로 일 처리가 가능한 직원에게 K를 배분하는 방식으로 짭니다. 매칭이 실패하면 다음 번호로 넘어가는 겁니다.

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main{
	
	static int N, M, K;
	static int time;
	static int match[];
	static int visitTime[];
	static List<Integer> adList[];
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 직원 수(1<=1,000)
		M = Integer.parseInt(st.nextToken());// 일의 수(1<=1,000)
		K = Integer.parseInt(st.nextToken());// 벌점의 합(1<=사람수)
		match = new int[M + 1];
		visitTime = new int[M + 1];
		adList = new ArrayList[N + 1];
		
		for(int i=1; i<=N; i++)
		{
			st = new StringTokenizer(br.readLine());
			int cnt = Integer.parseInt(st.nextToken());
			adList[i] = new ArrayList<>();
			for(int j=0; j<cnt; j++)
				adList[i].add(Integer.parseInt(st.nextToken()));
		}
		
		int jobCnt = 0;
		// 먼저 모든 직원에 대해 이분 매칭을 돌려 할 수 있는 일의 수를 구한다.
		for(int i=1; i<=N; i++)
		{
			++time;
			if(dfs(i))
				++jobCnt;
		}
		
		++time;// 다음 visit을 판단하기 위해 dfs전 +1을 미리 해줌
		// K번 더 매칭을 위해 직원마다 매칭이 불가할 때 까지 이분 매칭을 돌린다.
		for(int i=1; i<=N && K != 0; i++)
		{
			while(dfs(i) && K != 0)
			{// 매칭이 가능하면 계속 일을 매칭시켜 K를 감소시킴
				++jobCnt;
				++time;
				--K;
			}
		}
		
		System.out.print(jobCnt);
	}
	static boolean dfs(int person)
	{
		for(int job : adList[person])
		{
			if(visitTime[job] == time)
				continue;
			
			visitTime[job] = time;
			
			if(match[job] == 0 || dfs(match[job]))
			{
				match[job] = person;
				return true;
			}
		}
		
		return false;
	}
}