백준 11375 자바 - 열혈강호

// 열혈강호
package Platinum_IV_4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Ex11375 {

    static List<Integer>[] list;
    static boolean[] check;
    static int[] d;

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

        check = new boolean[m + 1];
        d = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            for (int j = 0; j < s; j++) {
                list[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        int cnt = 0;
        // 1 ~ n번 직원 순차대로 일 할당
        for (int i = 1; i <= n; i++) {
            Arrays.fill(check, false);
            if (dfs(i)) cnt++; // 일이 할당 되었으면, cnt++
        }
        System.out.println(cnt);
    }

    static boolean dfs(int here) {
        for (int nxt : list[here]) {
            if (!check[nxt]) {
                check[nxt] = true;
                // 비어 있거나 점유 노드에 더 들어갈 공간이 있는 경우
                if (d[nxt] == 0 || dfs(d[nxt])) {
                    d[nxt] = here;
                    return true;
                }
            }
        }
        return false;
    }
}

위 코드는 해당 문제에서 사용되는 알고리즘인 이분 매칭을 알아보다가 비슷한 문제의 풀이를 제공하신 아래의 블로그를 보고 작성했다. 

[알고리즘] 이분 매칭 (Bipartite Matching) 알고리즘 (Java) (tistory.com)

[알고리즘] 이분 매칭 (Bipartite Matching) 알고리즘 (Java)

이 블로그에서는 2188번: 축사 배정 (acmicpc.net)  문제로 풀었는데 내가 푼 열혈강호 문제와 풀이 방법은 똑같은 듯했다. 이번 문제는 블로그를 보고 풀었지만, 다음에 축사 배정 문제는 안 보고 풀어 봐야겠다.