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

#문제         

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

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

---

#문제 풀이        

 

이 문제는 이분 매칭 문제이다. 

예시를 통해 문제를 설명하겠다. 헷갈릴 수 있으니 일을 1 ~5로 표현하고 직원을 A,B,C,D,E로 표현하겠다.

예제 1을 보면

 

1. A는 1번 일과 2 번일을 할 수 있다. 일단 1번 일을 맡겠다고 치자.

A B C D E
1

 

2. B는 1번 일만 할 수 있다. 그래서 1 번 일을 맡고 있는 A가 다른 일을 맡을 수 있는지 확인한다. 확인하니 1 번 말고 2 번 일을 맡을 수 있다. B는 1 번일, A는 2 번일을 맡도록 하자.

A B C D E
2 1

 

3. C는 2, 3 번일을 할 수 있다. 2 번 일을 살펴보니 A가 맡고 있다. A가 다른 일을 맡을 수 있는지 확인한다. 확인하니 2 번 말고 1 번일을 맡을 수 있다. 그러나 1 번 일을 확인하니 B가 맡고 있다. B가 다른 일을 할 수 있는지 확인하니 없다. 그래서 B가 못 바꾸니 A도 못 바꾸고 C도 2 번일을 못하는 거다.

 그럼 3 번일을 살펴본다. 3 번일은 아무도 안 맡고 있으니 C가 3 번일을 맡든다.

A B C D E
2 1 3

 

4. D는 3,4,5 번 일을 할 수 있다. 3 번일을 살펴보니 C가 맡고 있다. C가 다른 일을 할 수 있는지 확인한다. 확인하니 2번 일을 할 수 있다. 2 번일을 확인하니 A가 맡고 있다. A가 다른 일을 맡을 수 있는지 확인한다. 확인하니 2 번 말고 1번일을 맡을 수 있다.  3번과정과 똑같은 걸 느끼나? 3번 과정대로 꼬리를 물면 B가 다른일을 할 수 없어. D는 3 번일을 못한다.  

그럼 4 번일을 살펴본다. 4 번 일은 아무도 안 맡고 있으니 D가 4 번 일을 맡는다.

A B C D E
2 1 3  4

 

 

5. E는 1 번 일을 할 수 있다. 1 번 일은 B가 맡고 있다. B는 다른 일을 할 수 없으니 E에게 일을 줄 수 없다. 고로 E는 아무것도 안한다. 결국 정답은 4이다.

 

 

 

---

#풀이 코드      

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int N, M;
    static List<Integer>[] adj;
    static int[] task;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        adj = new ArrayList[N + 1];
        task = new int[M + 1];
        visited = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
            int numTasks = scanner.nextInt();
            for (int j = 0; j < numTasks; j++) {
                adj[i].add(scanner.nextInt());
            }
        }

        int maxMatch = 0;
        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            if (dfs(i)) {
                maxMatch++;
            }
        }

        System.out.println(maxMatch);
        scanner.close();
    }

    static boolean dfs(int employee) {
        if (visited[employee]) {
            return false;
        }
        visited[employee] = true;

        for (int t : adj[employee]) {
            if (task[t] == 0 || dfs(task[t])) {
                task[t] = employee;
                return true;
            }
        }
        return false;
    }
}