[백준 2188] 축사 배정 / 자바 / 이분매칭

#문제         

레벨: P4
알고리즘: 이분매칭 
풀이시간: 1시간 
힌트 참조 유무: 유

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

---

#문제 풀이        

이분매칭이 처음이라면 
https://jsw5913.tistory.com/214

[백준 11375] 열혈강호 / 자바 / 이분 매칭

이 글을 먼저 읽고 오길 바란다.

 

[풀이방법]

 

• DFS 함수에서는 해당 소가 들어갈 수 있는 모든 축사를 확인한다:
  • 이미 방문한 축사는 건너뛴다.
  • 빈 축사를 발견하면 바로 매칭한다.
  • 이미 다른 소가 배정된 축사라면, 그 소를 다른 축사로 옮길 수 있는지 재귀적으로 확인한다.
• 매칭에 성공할 때마다 결과값을 1 증가시킨다.

 

---

#풀이 코드      

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static ArrayList<Integer>[] graph;
    static int[] match;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        graph = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        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++) {
                int shed = Integer.parseInt(st.nextToken());
                graph[i].add(shed);
            }
        }
        
        match = new int[M+1];
        int result = 0;
        
        for (int i = 1; i <= N; i++) {
            visited = new boolean[M+1];
            if (dfs(i)) result++;
        }
        
        System.out.println(result);
    }
    
    static boolean dfs(int cow) {
        for (int shed : graph[cow]) {
            if (visited[shed]) continue;
            visited[shed] = true;
            
            if (match[shed] == 0 || dfs(match[shed])) {
                match[shed] = cow;
                return true;
            }
        }
        return false;
    }
}

 

---

#비슷한 문제      

https://jsw5913.tistory.com/214

[백준 11375] 열혈강호 / 자바 / 이분 매칭