[백준] 11376 열혈강호2

문제

---

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

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

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

 

 

풀이

---

열혈강호 1번 문제를 2번 돌리는 방식을 이용하였다.

https://conpulake.tistory.com/261

[백준] 11375 열혈강호 - 이분매칭

한번 돌리면서 하나의 일을 찾으면 cnt++을 해주어서 해당 직원이 몇개의 일을 하고있는지 셌다.

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();

	static int n, m;
	static List<Integer>[] person;
	static int[] work, cnt;
	static boolean[] visited;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		person = new List[n + 1];
		cnt = new int[n + 1];
		work = new int[m + 1];
		visited = new boolean[m + 1];
		
		for(int i = 1 ; i <= n ; i++) {
			st = new StringTokenizer(br.readLine());
			
			person[i] = new ArrayList<>();
			
			int size = Integer.parseInt(st.nextToken());
			for(int j = 0 ; j < size ; j++) {
				person[i].add(Integer.parseInt(st.nextToken()));
			}
		}
		
		int answer = 0;
		int num = 1;
		while( num <= n ) {			
			if(dfs(num)) answer++;
			else {
				num++;
				Arrays.fill(visited, false);
				continue;
			}
			
			if(cnt[num] == 2) {
				num++;
				Arrays.fill(visited, false);
			}
		}
		
		
		System.out.println(answer);
	}
	
	static boolean dfs(int here) {
		for(int w : person[here]) {
			if(visited[w] || work[w] == here) continue;
			
			visited[w] = true;
			
			if(work[w] == 0 || dfs(work[w])) {
				work[w] = here;
				cnt[here]++;
				return true;
			}
		}
		
		return false;
	}

}