[백준] 9576: 책 나눠주기 - JAVA

in Algorithm on 그리디 알고리즘

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

풀이

이분 매칭 알고리즘을 이용해 풀 수 있는 문제였다.

ArrayList에 학생마다 배정할 수 있는 책들을 저장한다.

책의 주인을 담을 수 있는 배열을 만들고, 방문 처리를 할 배열을 만들었다.

m명의 학생을 탐색하면서 dfs를 하는데

배정되지 않은 책의 경우 해당 학생에 배정하고,

배정된 경우 해당 책의 주인으로 등록된 사람을 dfs탐색하여 다른 책에 배정할 수 있는 지 확인하고 가능할 경우 새로 배정한다.

메모리: 100992KB

시간: 1064ms

언어: Java 11

코드

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

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

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

        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < t; tc++) {
            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 <= m + 1; i++) {
                list.add(new ArrayList<>());
            }

            for (int i = 1; i < m + 1; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                for (int j = a; j <= b; j++) {
                    list.get(i).add(j);
                }
            }

            // 책마다 배정받은 주인을 저장
            owner = new int[n + 1];
            visit = new boolean[n + 1];

            int cnt = 0;
            // 학생에게 책 배정
            for (int i = 1; i <= m; i++) {
                Arrays.fill(visit, false);
                // 배정되었으면 cnt++
                if (dfs(i)) {
                    cnt++;
                }
            }

            sb.append(cnt).append("\n");
        }

        System.out.println(sb);
    }

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

            // 배정되지 않았거나, 배정되어있는 학생에게 다른 책을 줄 수 있을 경우
            if (owner[num] == 0 || dfs(owner[num])) {
                owner[num] = idx;
                return true;
            }
        }

        return false;
    }

}