(Elice / 이분매칭 / Java) 이 도끼가 너의 도끼냐?

이 도끼가 너의 도끼냐?

각자 도끼를 하나씩 가지고 있는 나무꾼들이 호수를 둘러싼 나무들을 베고 있었습니다. 그런데 우연히 나무꾼들은 똑같은 시간에 도끼를 놓치고 말았고, 모든 도끼들은 동시에 호수에 빠지고 말았습니다.

호수에서 올라온 산신령은 도끼를 나무꾼들에게 돌려주었습니다. 애석하게도 N명의 나무꾼들은 자신의 도끼가 어떤것인지 알지 못했습니다. 왜냐하면 그들은 도끼를 어제 공동구매를 했기 때문입니다. 그들은 다같이 공동구매를 한 도끼니 원래의 주인을 구분하지 않고 각자 한개씩 가지기로 했습니다.

그래도 산신령은 그들에게 자신의 도끼라고 생각되는 도끼들을 얘기해 보라고 했습니다. 그들은 원래의 자기 것이라고 생각이 드는 도끼들을 여러 개 선택했습니다. 산신령은 나무꾼들의 요구를 최대한 만족시키고 싶습니다.

산신령을 도와 본인의 것인 것 같다고 생각하는 도끼를 가질 수 있는 나무꾼의 최대 수를 출력하는 프로그램을 작성하세요.

 

지시사항

입력

• 첫째 줄에는 공동구매한 나무꾼의 수인 정수 N과 도끼 의심 개수 M을 입력합니다.

                                                                   (1≤N≤50)

                                                                 (0≤M≤2,500)

• 둘쨋 줄부터 M+1번째 줄 까지는 각각 한 줄마다 a b가 주어지는데, 이는 a번 나무꾼이 b번 도끼가 자신의 것이라고 생각한다는 의미입니다.
• 도끼와 나무꾼의 번호는 1보다 크거나 같고, N보다 작거나 같습니다. 두 나무꾼 또는 두 도끼가 같은 번호를 갖는 경우는 없습니다.

출력

• 최대로 만족될 수 있는 나무꾼의 수를 출력합니다.

입력 예시

5 15
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
3 1
3 4
4 5
4 4
5 5
3 2

출력 예시

5

소스 코드

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

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[n+1];
		check = new boolean[n+1];
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
		}
		
		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;
	}
}