[백준 온라인 저지] 11375. 열혈강호

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

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

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

 

1. 입력

- 첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

- 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

 

2. 출력

- 첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

 

3. 예제

 

4. 코드

import java.util.*;
import java.io.*;
class Main{
    static int n, m; // 직원, 직무의 수
    static List<List<Integer>> ican = new ArrayList<List<Integer>>(); // 직원이 할 수 있는 일
    static int[] num; // i번째 직무를 담당한 직원의 번호
    static boolean[] assigned; // i번째 직무의 담당이 정해졌다면 true
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.valueOf(st.nextToken()); m = Integer.valueOf(st.nextToken());
        num = new int[m+1]; assigned = new boolean[m+1];
        for(int i=0 ; i<=n ; i++)
            ican.add(new ArrayList<>());
        for(int i=1 ; i<=n ; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.valueOf(st.nextToken());
            for(int j=0 ; j<a ; j++)
                ican.get(i).add(Integer.valueOf(st.nextToken()));
        }
        int count = 0;
        for(int i=1 ; i<=n ; i++){
            Arrays.fill(assigned, false);
            if(dfs(i)) count++;
        }
        System.out.print(count);
    }
    
    static boolean dfs(int x){
        for(int i=0 ; i<ican.get(x).size() ; i++){
            int y = ican.get(x).get(i);
            if(assigned[y]) continue;
            assigned[y] = true;
            if(num[y]==0 || dfs(num[y])){
                num[y] = x;
                return true;
            }
        }
        return false;
    }
}

- 97520KB, 1196ms