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

#11377 열혈강호 3

난이도 : 플레 3

유형 : 이분 매칭

11377번: 열혈강호 3

▸ 문제

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

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 단, N명 중에서 K명은 일을 최대 2개할 수 있다.

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

▸ 입력

첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N)

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

▸ 출력

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

 

문제 풀이  

백준 11376번 열혈강호2의 연장된 문제이다. 처음에 아이디어가 생각이 잘 안났는데, 질문 글에 어떤 분이 그린 그림을 보고 단번에 이해가 갔다. 네트워크 유량으로 기존의 그래프에서 하나의 노드를 더 생성하여 K개의 용량을 늘려주면 된다.

 

용량 K인 노드 생성하기

 

 

1. src → 직원 → 일 → sink

처음에는 다음의 경로를 통해 총 용량이 N인 이분매칭을 해준다.

• 1 - b
• 2- a
• 3 - e

 

첫번째 매칭

 

2. src → X → 직원 → 일 → sink

그런 다음 K의 용량을 가진 노드를 생성하여 추가로 최대 매칭을 구해주면 된다.

• 1 - a, c
• 2 - b
• 3 - e

두번째 매칭

 

풀이 코드 

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<=2*n; i++) {
			Arrays.fill(check, false);
			if(i<=n) {
				if(dfs(i)) cnt++;
			}
			else{
				if(dfs(i-n) && k>0) {
					k--;
					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;
	}
}