BOJ - 2188 ) 축사배정

---

https://www.acmicpc.net/problem/2188

2188번: 축사 배정

 

---

각 소가 원하는 축사가 존재한다 ( 존재하지 않을수도 있음 )

 

일단은 배정후 변경하는 이분매칭알고리즘을 사용하자.

---

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main {
  public static int m,n,result[];
  public static boolean check[];
  public static ArrayList<Integer> node[];
  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());
    
    node = new ArrayList[n+1];
    // 축사가 어느 소에 배정이 되어있는지 정보 RESULT배열 -> 0은 없는것 꼭 1부터 시작
    result = new int[m+1];
    for(int i = 1 ; i <= n ; i++){node[i] = new ArrayList<>();}
    for(int i = 0 ; i < n ; i ++){
      st = new StringTokenizer(br.readLine());
      int cnt = Integer.parseInt(st.nextToken());
      while(cnt-->0){
        int wantHoust = Integer.parseInt(st.nextToken());
        node[i+1].add(wantHoust);
      }
    }

    int answer =0;
    for(int i = 1 ; i <= n ; i++){
      check = new boolean[m+1];
      if(bipartiteMatching(i)){
        answer++;
      } 
    }
    System.out.print(answer);
  }

  public static boolean bipartiteMatching(int x){
    
    for(int i = 0 ; i < node[x].size() ; i++){
      // 원하는 집
      int want = node[x].get(i);
      if(!check[want]){
        // 방문안했다면 방문처리 해주어 중복방지
        check[want] = true;
        // 내가 들어가고싶은 축사가 비어있으면 배정 or 앞에있는 축사의 배정이 바뀔수 있다면 재귀
        if(result[want]==0 || bipartiteMatching(result[want])){
          result[want] = x;
          return true;
        }
      }
    }

    return false;
  }
}

---