[JAVA] 백준 2188 - 축사 배정

문제

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

2188번: 축사 배정

해결 방법

• DFS로 해결했는데 이 알고리즘을 이분매칭이라고 하는것 같음 => 나중에 다시 알아봄
• 예제를 풀며 해결 방법 정리
• ex) 입력이 아래와 같이 들어왔다고 가정

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

• 1번 소는 2, 5번 축사에 가고 싶어함
• 확인 후 비어있는 축사가 있으면 바로 집어 넣음
• 1, 2, 3번 소는 비어 있는 축사에 바로 들어갈 수 있음

• 이제 4번 소가 들어가려고 보니 바로 들어갈 수 있는곳이 없음
  1. 4번 소가 원하는 축사에 넣어봄
  2. 아래와 같이 1번 축사에 4번 소를 넣음
  3. 3번 소가 자리가 없어짐

• 이 상황에서 3번 소는 1번 축사가 아닌 다른 원하는 축사에 넣음
  • 5번으로 들어가게 됨

• 이제 5번 소를 넣어야 됨
  1. 원하는 축사가 다 차있으므로 1번 축사에 넣어봄
  2. 4번 소가 갈 곳이 없어짐

• 4번소가 갈 곳이 없으니 원상복귀 후 5번소를 2번 축사에 넣어봄

• 5번소가 2번축사로 가고, 1번 소가 5번 축사로 가는데까지 성공
• 3번 소를 1, 5번 중 하나에 넣어야 되는데 5번 축사에는 방금 1번이 옮겨갔고, 1번 축사는 전에 5번 소가 갔을 때, 모두 이동할 수 없었음
  • 3번 소 이동 불가
  • 5번 소는 축사에 넣을 수 없음

코드

import java.util.Scanner;

public class p2188 {

    static int n, m;
    static int[][] arr;
    static int[] house;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            arr[i][0] = sc.nextInt();
            for (int j = 1; j <= arr[i][0]; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        house = new int[m + 1];
        for(int i = 1 ; i <= n ; i ++) {
            boolean direct = false;
            for(int j = 1 ; j <= arr[i][0] ; j ++) {
                if(house[arr[i][j]] == 0) {
                    house[arr[i][j]] = i;
                    direct = true;
                    break;
                }
            }
            if(direct == false) {
                visited = new boolean[m + 1];
                dfs(i);
            }
        }

        int ans = 0;
        for(int i = 1 ; i <= m ; i ++) {
            System.out.println(house[i]);
            if(house[i] != 0) ans ++;
        }

        System.out.println(ans);
    }
    static boolean dfs(int index) {
        for(int i = 1 ; i <= arr[index][0] ; i ++) {
            if(visited[arr[index][i]] == false) {
                visited[arr[index][i]] = true;
                if(house[arr[index][i]] == 0 || dfs(house[arr[index][i]]) == true) {
                    house[arr[index][i]] = index;
                    return true;
                }
            }
        }
        return false;
    }
}