[Java] 백준 14907. 프로젝트 스케줄링

📌 문제 링크 - https://www.acmicpc.net/problem/14907

 

 

---

 

 

 

 

 

 

문제

퍼트라고 부르는 프로젝트 관리 기법은 큰 프로젝트를 작업 개수로 분할, 각 작업에서 요구되는 시간 계산, 다른 작업이 완료될 때까지 작업이 시작될 수 없도록 하는 결정을 포함한다. 이때 프로젝트를 차트 형식으로 표현할 수 있다.

 

예를 들어, 입력 예제의 데이터를 사용했을 때 차트는 A, B, C, D, E, F라는 작업을 갖고 각각 5, 3, 2, 2, 4, 2일이 걸리며, C와 D가 완료될 때까지 작업 E는 시작되지 않고, A가 수행되었다면 D와 B는 병렬로 수행 될 수 있다. 퍼트 차트에 따라 프로젝트를 완성하는데 걸리는 최소 시간을 계산하는 프로그램을 작성하시오.

 

 

입력

입력은 1줄에서 26줄까지 입력될 수 있으며, 각각은 다른 작업 (위 예제에서 말하자면 A, B, C, …) 을 포함한다. 각 줄에는 다음과 같은 내용이 포함된다.

1. 작업 이름을 나타내는 영문 대문자 하나,
2. 작업을 완료하는데 요구되는 날짜를 나타내는 1,000보다 작거나 같은 자연수
3. 0개에서 25개 사이의 덧붙여지는 영문 대문자 (띄어쓰기 없이 붙어 있음)는 이 작업을 시작하기 전에 완료해야만 하는 작업을 나타낸다.

항상 모든 작업을 완료할 수 있는 경우만 입력으로 주어진다.

 

 

출력

첫째 줄에 모든 작업을 완료하는데 걸리는 시간의 최솟값을 출력한다.

 

 

 

 

---

 

 

풀이

위상정렬로 풀 수 있다. 

 

 

 

이전에 수행해야 할 작업이 없는 작업들을 먼저 큐에 넣고(예제에서는 A), 이를 차례로 수행하면서 다음 작업들의 이전 작업 개수를 줄여준다. 동시에, 해당 작업이 끝났을 때 다음 작업을 시작하기까지 걸리는 시간을 갱신한다.

 

예를 들어, 작업 E를 수행하려면 C와 D가 먼저 완료되어야 한다. D는 7일(5+2), C는 10일(5+3+2)이 걸리므로, E는 두 작업 중 더 오래 걸린 10일 후에 시작 가능하다. 따라서, 이전 작업들 중 가장 오래 걸린 시간을 반영하여 다음 작업의 시작 시간을 결정한다.

 

이 과정을 모든 작업에 대해 반복하면서, 총 작업 시간을 갱신한다.

작업들은 병렬로 수행될 수 있으므로, 마지막으로 완료된 작업 중 가장 오래 걸린 시간이 모든 작업을 완료하는데 걸리는 시간의 최솟값이 된다.

 

---

 

 

코드

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

// https://www.acmicpc.net/problem/14907
public class Main_14907 {
    private static final int N = 26;  // 작업 최대 개수
    private static int[] prev, times; // 이전 작업 개수, 작업을 완료하는데 요구되는 시간
    private static List<List<Integer>> workList; // 작업


    public static void main(String[] args) throws IOException {
        init();

        int totalTime = getTime();
        System.out.print(totalTime);
    }//main


    private static int getTime() {
        int totalTime = 0; // 모든 작업을 완료하는데 걸리는 시간
        int[] prevTimes = new int[N]; // 이전 작업에 걸린 시간
        Queue<Integer> q = new LinkedList<>();

        for(int i=0; i<N; i++) {
            // 이전 작업이 없음
            if(prev[i] == 0 && times[i] != -1) {
                q.offer(i);
            }
        }

        int cur, time;
        while(!q.isEmpty()) {
            cur = q.poll(); // 현재 작업
            time = prevTimes[cur] + times[cur]; // 걸린 시간           
            totalTime = Math.max(totalTime, time); // 총 완료 시간

            // 다음 작업 가능한지 확인
            for(int next : workList.get(cur)) {
                prevTimes[next] = Math.max(prevTimes[next], time);
                
                if(--prev[next] == 0) {
                    q.offer(next);
                }
            }
        }

        return totalTime;
    }//getTime


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        prev = new int[N]; // 이전 작업 개수
        times = new int[N]; // 작업을 완료하는데 요구되는 시간
        workList = new ArrayList<>(N); // 작업

        for(int i=0; i<N; i++) {
            workList.add(new ArrayList<>());
            times[i] = -1;
        }

        StringTokenizer st;
        for(int i=0; i<N; i++) {
            String input = br.readLine();
            if(input == null || input.isEmpty()) break;

            st = new StringTokenizer(input);
            int name = st.nextToken().charAt(0) - 'A'; // 작업 이름을 나타내는 영문 대문자
            int time = Integer.parseInt(st.nextToken()); // 작업을 완료하는데 요구되는 시간
            times[name] = time;

            // 이 작업을 시작하기 전에 완료해야만 하는 작업이 있음
            if(st.hasMoreTokens()) {
                char[] prevWorks = st.nextToken().toCharArray();
                for(char work : prevWorks) {
                    prev[name]++;
                    workList.get(work - 'A').add(name);
                }
            }

        }

        br.close();
    }//init


}//class