[ Baekjoon ][JAVA][2188] 축사배정

www.acmicpc.net/problem/2188

2188번: 축사 배정

문제

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

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

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

입력

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

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

출력

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

예제 입력

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

예제 출력

4

접근

네트워크 유량과 이분매칭 두 방법으로 풀 수 있다. 하지만 축사배정은 유량이 1로 동일한 이분매칭문제이므로 DFS를 이용한 포드-풀커슨 알고리즘을 적용하기만 하면 문제가 쉽게 풀릴 수 있다. 까먹지않게 확실히 외워두어 다른 응용문제 더 풀러가자!

코드

// BFS로 푸는 것이 에드몬드 카프 (네트워크 유량)
// DFS로 푸는 것이 포드-풀커슨 (이분매칭)
import java.io.*;
import java.util.*;
class Main{
    static int N, M;
    static boolean[] visited;
    static int[][] edges;
    static int[] aMatch, bMatch;
    public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        edges = new int[N][M];
        for(int cowNum=0; cowNum<N; cowNum++){
            st = new StringTokenizer(br.readLine());
            int barnSize = Integer.parseInt(st.nextToken());
            for(int i=0; i<barnSize; i++){
                int barnNum = Integer.parseInt(st.nextToken())-1;
                edges[cowNum][barnNum] = 1;
            }
        }
        System.out.println(bipartiteMatching());
    }
    // 집합 A의 정점 a에서 B의 매칭되지 않은 정점으로 가는 경로를 찾는 함수
    public static boolean dfs(int a){
        if(visited[a]) return false;	// 재방문 cut. 매칭 수정 시 이 한줄의 코드가 어떻게 작용하는지 유의
        visited[a] = true;
        for(int b=0; b<M; ++b){
            if(edges[a][b]==1){
                //b가 아직 매칭되지 않을 때
                if(bMatch[b] == -1){
                    aMatch[a] = b;
                    bMatch[b] = a;
                    return true;
                }
                //b가 이미 매칭되어 있다면 bMatch[b]에서부터 시작해 경로를 찾는다. 찾았을 경우 재귀 호출한 부분에서 경로를 수정한다.
                if(dfs(bMatch[b])){
                    //dfs 호출(재귀호출)에서 경로를 수정했으니 b에 연결된 정점이 없으므로 연결해준다.
                    aMatch[a] = b;
                    bMatch[b] = a;
                    return true;
                }
            }
        }
        return false;
    }
    
    public static int bipartiteMatching(){
        aMatch = new int[N];
        bMatch = new int[M];
        Arrays.fill(aMatch, -1);
        Arrays.fill(bMatch, -1);
        
        int size = 0;
        for(int start = 0; start < N; start++){
            visited = new boolean[N];
            //증가경로, 즉 매칭을 찾은 경우 1의 유량을 증가시킨다.
            //증가 경로 찾을 때마다 +1?
            if(dfs(start)) ++size;
        }
        return size;
    }
}