[Java] 백준 11376번 열혈강호2

이분 매칭으로 문제를 해결하였습니다.

N명의 직원이 있고 해야할 일이 M개가 있을 때
직원들이 할 수 있는 일들이 정해져있고 두개의 일만 할 수 있습니다.
이 때 일을 잘 분배해서 가장 많이 할 수 있는 일의 수를 찾는 문제입니다.

A집단과 B집단을 매칭해야하는 경우이므로 이분매칭을 사용할 수 있습니다.

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

각 사람당 DFS를 두번 돌리므로서 2개씩 일을 배치해 줄 수 있게 됩니다.

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;
			}
			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;
	}
}