[백준 온라인 저지] 2188. 축사 배정

농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다.

첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.

농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다.

 

1. 입력

- 첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)

- 둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.

 

2. 출력

- 첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.

 

3. 예제

 

4. 코드

import java.util.*;
import java.io.*;
class Main{
    static int n, m; // 소, 축사의 수
    static List<List<Integer>> wish = new ArrayList<List<Integer>>(); // i번째 소가 원하는 축사
    static boolean[] occupied; // 배정됐다면 true
    static int[] d; // i번째 축사에 배정된 소의 번호
    
    public static void main(String[] agrs) 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());
        occupied = new boolean[m+1];
        d = new int[m+1];
        for(int i=0 ; i<=n ; i++)
            wish.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++)
                wish.get(i).add(Integer.valueOf(st.nextToken()));
        }
        int count = 0;
        for(int i=1 ; i<=n ; i++){
            Arrays.fill(occupied, false);
            dfs(i);
        }
        for(int i=1 ; i<=m ; i++)
            if(d[i]!=0) count++;
        System.out.print(count);
    }
    
    static boolean dfs(int x) {
        for(int i=0 ; i<wish.get(x).size(); i++) {
            int y = wish.get(x).get(i);
            if(occupied[y]) continue;
            occupied[y] = true;
            if(d[y]==0 || dfs(d[y])) {
                d[y] = x;
                return true;
            }
        }
        return false;
    }
}

- 17528KB, 240ms