[Java] 백준 11375번 열혈강호

이분매칭 문제입니다.
각자가 일을 한개 씩 할 수 있을 때 최대한 많이 매칭시켜야 합니다.

이분 매칭 알고리즘을 사용해서 매칭을 시켜줍니다.

1. 매칭이 되어 있지 않으면 매칭
2. 매칭이 되어 있으면 매칭되어 있는 곳에서 다른 곳에 매칭이 되는지 확인
3. 불가능하면 다른 곳 매칭이 가능한지 확인
4. 모든 곳이 매칭 불가능하면 그 위치는 매칭이 안되는 곳으로 확인

위의 과정을 반복해서 모두 매칭을 하고 매칭된 수를 출력해줍니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int ans;
	static int n;
	static int m;
	static int work[];
	static int visit[];
	static ArrayList<ArrayList<Integer>> al = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		ans = 0;
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		work = new int[m + 1];
		visit = new int[n + 1];

		for (int i = 0; i <= n; ++i) {
			ArrayList<Integer> temp = new ArrayList<>();
			al.add(temp);
		}

		for (int i = 1; i <= n; ++i) {
			st = new StringTokenizer(br.readLine());
			int cnt = Integer.parseInt(st.nextToken());
			for (int j = 0; j < cnt; ++j) {
				al.get(i).add(Integer.parseInt(st.nextToken()));
			}
		}

		for (int i = 1; i <= n; ++i) {
			if(DFS(i) == 1) {
				++ans;
			}
			for(int j=1; j<=n; ++j) {
				visit[j] = 0;
			}
		}

		bw.write(ans + "\n");
		bw.close();
	}

	public static int DFS(int user) {
		if (visit[user] == 1) {
			return 0;
		}
		visit[user] = 1;
		
		for (int i = 0; i < al.get(user).size(); ++i) {
			int job = al.get(user).get(i);

			int next = work[job];
			if (work[job] == 0 || DFS(next) == 1) {
				work[job] = user;
				return 1;
			}
		}
		return 0;
	}
}