[백준, BOJ 11375] 열혈강호 (java)

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

메모리: 139,832 KB , 시간: 796 ms

사용 알고리즘: 그리디 알고리즘, 이분 매칭

728x90

---

처음 풀이는

직원 객체인 Person의 size에 본인이 담당할 수 있는 작업(list) 중 아직 담당 직원이 정해지지 않은 작업의 개수를 저장하도록 하였다.

그리고 매번 size가 가장 작은 직원이 담당할 수 있는 작업 중 아직 담당 직원이 정해지지 않은 아무 작업에 해당 직원을 할당해 주는 방식을 사용했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Person implements Comparable<Person> {

        List<Integer> list;
        int size;

        Person() {
            list = new ArrayList<>();
            size = 0;
        }

        void add(int w) {
            list.add(w);
            size++;
        }

        @Override
        public int compareTo(Person p) {
            return this.size - p.size;
        }
    }

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 직원 리스트
        List<Person> people = new ArrayList<>();
        people.add(new Person());

        // 각 작업별로 수행할 수 있는 직원 리스트
        List<List<Integer>> works = new ArrayList<>();
        for (int i = 0; i <= M; i++) {
            works.add(new ArrayList<>());
        }

        int num, w;
        for (int i = 1; i <= N; i++) {
            people.add(new Person());
            st = new StringTokenizer(br.readLine());
            num = Integer.parseInt(st.nextToken());
            for (int j = 0; j < num; j++) {
                w = Integer.parseInt(st.nextToken());
                people.get(i).add(w);
                works.get(w).add(i);
            }
        }

        List<Person> list = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            list.add(people.get(i));
        }

        // 수행한 작업 체크
        boolean[] isWorked = new boolean[M + 1];

        int answer = 0;

        Person p;
        while(!list.isEmpty()) {

            // 정렬
            Collections.sort(list);

            p = list.get(0);
            list.remove(0);

            // 현재 직원이 수행할 수 있는 작업이 남아있지 않다면 넘김
            if(p.size == 0) continue;

            for(int work : p.list) {
                // 이미 수행한 작업이면 넘김
                if(isWorked[work]) continue;

                isWorked[work] = true;
                answer++;

                for(int idx : works.get(work)) {
                    people.get(idx).size--;
                }

                break;
            }
        }

        System.out.println(answer);
    }
}

 

그리디 하게 푼 위 코드로 맞았습니다를 받긴 했는데,

해당 문제에 등록되어 있지 않은 예외가 있을 수도 있겠다는 생각이 들긴 했다.

 

그래서 이 문제의 알고리즘 분류에 있는 이분 매칭 알고리즘을 찾아봤고

해당 블로그를 참고해서 다시 풀어보았다.

 

메모리: 121,368MB, 시간: 2,248 ms

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static List<List<Integer>> workList;
    static int[] task;
    static boolean[] check;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 직원별 담당할 수 있는 작업 리스트
        workList = new LinkedList<>();
        for (int i = 0; i <= N; i++) {
            workList.add(new LinkedList<>());
        }

        int n, work;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            for (int j = 0; j < n; j++) {
                work = Integer.parseInt(st.nextToken());
                workList.get(i).add(work);
            }
        }

        // 해당 작업을 맡은 직원 정보
        task = new int[M + 1];

        // 해당 작업을 처리할 직원이 정해졌는지 확인
        check = new boolean[M + 1];

        int answer = 0;
        for (int i = 1; i <= N; i++) {
            Arrays.fill(check, false);
            if(dfs(i)) answer++;
        }

        System.out.println(answer);
    }

    static boolean dfs(int p) {

        for(int work : workList.get(p)) {
            // 이미 처리할 직원이 정해진 작업이면 다른 작업 확인하러
            if(check[work]) continue;

            check[work] = true;

            // 아직 담당 직원이 정해지지 않은 작업이거나.
            // 담당 직원이 다른 작업을 맡을 수 있는 경우
            if(task[work] == 0 || dfs(task[work])) {
                task[work] = p;
                return true;
            }
        }

        return false;
    }
}

 

시간이 3배 가량 더 걸리긴 한다.

그래도 검증된 알고리즘이니 기억해 두어야겠다.