[BaekJoon] 14907 프로젝트 스케줄링 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static final int ALPHABET_SIZE = 26;

    static int answer;
    static int[] elapseTimes;
    static int[] workTimes;
    static int[] precedeWorkCount;
    static Set<Character> works;
    static Map<Character, List<Character>> followingWorks;

    static void input() {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String str;

        try {
            works = new HashSet<>();
            elapseTimes = new int[ALPHABET_SIZE];
            workTimes = new int[ALPHABET_SIZE];
            precedeWorkCount = new int[ALPHABET_SIZE];
            followingWorks = new HashMap<>();

            while ((str = br.readLine()) != null) {
                if (str.isEmpty()) {
                    break;
                }
                st = new StringTokenizer(str);

                char workAlphabet = st.nextToken().charAt(0);
                int workTime = Integer.parseInt(st.nextToken());
                String precedeWorks = "";
                if (st.hasMoreElements()) {
                    precedeWorks = st.nextToken();
                }

                workTimes[workAlphabet - 'A'] = workTime;
                works.add(workAlphabet);

                for (int idx = 0; idx < precedeWorks.length(); idx++) {
                    followingWorks.computeIfAbsent(workAlphabet, key -> new ArrayList<>())
                            .add(precedeWorks.charAt(idx));
                    precedeWorkCount[precedeWorks.charAt(idx) - 'A']++;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /*
     * 어떤 작업을 수행하기 위해서 선행되어야 하는 작업들이 존재하기 때문에 위상 정렬을 이용하여 수행될 작업의 순서를 구한다
     * 그런데 같은 우선순위를 가지는 작업은 병렬로 수행이 가능하기 때문에 작업 시간은 아래와 같이 구한다
     *  - 현재 작업 이전에 선행되어야 하는 작업들까지의 경과 시간 중 가장 오래 걸리는 시간 + 현재 작업의 작업 시간
     *  - 이전까지 구한 현재 작업까지의 경과 시간
     *  - 두 시간 중 더 큰 시간이 현재 작업까지의 경과 시간이 된다
     *      - 선행되어야 하는 작업들이 모두 완료되어야 현재 작업을 처리할 수 있기 때문에 선행되어야 하는 작업 중 가장 오래 걸리는 작업 다음에 현재 작업이 진행된다
     *      - 그렇기 때문에 큰 값을 경과 시간으로 갖는다
     * 이와 같은 방법으로 최소 경과 시간을 구한다
     */
    static void solution() {
        calculateTotalElapseTime();
        System.out.println(answer);
    }

    static void calculateTotalElapseTime() {
        List<List<Character>> sortedWorkOrder = new ArrayList<>();
        sortedWorkOrder.add(new ArrayList<>());

        Queue<Character> queue = new LinkedList<>();
        for (char work : works) {
            if (precedeWorkCount[work - 'A'] == 0) {
                queue.offer(work);
                elapseTimes[work - 'A'] = workTimes[work - 'A'];
                answer = Math.max(answer, elapseTimes[work - 'A']);
            }
        }

        while (!queue.isEmpty()) {
            char cur = queue.poll();

            if (followingWorks.containsKey(cur)) {
                for (char nextWork : followingWorks.get(cur)) {
                    precedeWorkCount[nextWork - 'A']--;
                    if (precedeWorkCount[nextWork - 'A'] == 0) {
                        queue.offer(nextWork);
                    }

                    elapseTimes[nextWork - 'A'] = Math.max(elapseTimes[nextWork - 'A'],
                            elapseTimes[cur - 'A'] + workTimes[nextWork - 'A']);
                    answer = Math.max(answer, elapseTimes[nextWork - 'A']);
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }
}