[백준] 2188: 축사 배정 - JAVA

29 Aug 2023 in Algorithm on 기타

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

풀이

이분 매칭 알고리즘으로 푸는 문제였다.

소가 각각 희망하는 축사 번호가 주어진다.

이것을 ArrayList<ArrayList> 에 저장했다.

그 후 1번 소부터 n번 소까지 dfs탐색을 하는데

이때 각 소가 희망하는 축사의 번호를 반복 탐색으로 체크하여 이미 축사가 선점되었으면

그 축사의 주인이 되는 소를 찾아 다른 축사에 들어갈 수 있는지 판단하는 과정을 거친다.

해당 번호의 소가 축사를 배정받을 수 있었다면 카운트를 1늘려준다.

---

메모리: 17364KB

시간: 252ms

언어: Java 11

코드

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

public class Main {
    static ArrayList<ArrayList<Integer>> list;
    static boolean[] visit;
    static int[] cow;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        for (int i = 1; i <= n + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            for (int j = 0; j < s; j++) {
                int a = Integer.parseInt(st.nextToken());
                list.get(i).add(a);
            }
        }

        visit = new boolean[m + 1];
        cow = new int[m + 1];

        int cnt = 0;
        for (int i = 1; i < n + 1; i++) {
            Arrays.fill(visit, false);
            if (dfs(i)) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }

    private static boolean dfs(int idx) {
        for (int cage : list.get(idx)) {
            if (visit[cage]) {
                continue;
            }
            visit[cage] = true;

            if (cow[cage] == 0 || dfs(cow[cage])) {
                cow[cage] = idx;
                return true;
            }
        }

        return false;
    }

}