[백준 2056] 작업 (Java) - 위상정렬, 다이나믹 프로그래밍

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

작업

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

입력

첫째 줄에 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

출력

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

예제 입력 1 복사

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

예제 출력 1 복사

23

힌트

• 1번 작업 : 0~5 
• 2번 작업 : 5~6
• 3번 작업 : 6~9 
• 4번 작업 : 5~11
• 5번 작업 : 11~12
• 6번 작업 : 11~19
• 7번 작업 : 19~23

---

풀이

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

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 수행해야 할 작업

        ArrayList<Work>[] A = new ArrayList[N+1]; // 작업번호 1번부터 시작
        Work[] works = new Work[N+1]; // 작업정보 저장
        int[] indegree = new int[N+1]; // 진입차수 배열
        int[] spent = new int[N+1]; // i번 작업 수행하는데 소요되는 시간

        // 인접노드 리스트 초기화 하기
        for (int i=1; i<N+1; i++){
            A[i] = new ArrayList<>();
        }

        // 작업 정보 입력받기
        StringTokenizer st;
        for (int i=1; i<N+1; i++){
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken()); // 걸리는 시간
            works[i] = new Work(i, time); // 작업정보 저장

            int priorNumbers = Integer.parseInt(st.nextToken()); // 선행관계에 있는 작업들의 개수
            indegree[i] = priorNumbers; // 진입차수 저장

            // 선행작업 저장
            while (priorNumbers-->0){
                int prior = Integer.parseInt(st.nextToken()); // 선행 작업번호
                A[prior].add(works[i]); // prior 번 작업 -> i번 작업수행
            }
        }

        // 위상정렬 시작
        Queue<Work> q = new LinkedList<>();

        // 진입차수 0인 작업 큐에 넣기
        for (int i=1; i<N+1; i++){
            if (indegree[i] == 0){
                q.offer(works[i]);
            }
        }

        while (!q.isEmpty()){
            Work now = q.poll();
            spent[now.index] += now.time;

            for (Work next : A[now.index]){
                indegree[next.index]--; // 진입차수 감소
                spent[next.index] = Math.max(spent[next.index], spent[now.index]);
                if (indegree[next.index] == 0){
                    q.offer(next); // 진입차수 감소 후 0이 되었다면 큐에 넣음
                }
            }
        }

        int result = 0;
        for (int i=1; i<N+1; i++){
            result = Math.max(result, spent[i]);
        }

        System.out.println(result);
    }
}
class Work{
    int index; // 작업번호
    int time; // 걸리는 시간

    public Work(int index, int time){
        this.index = index;
        this.time = time;
    }
}

• 위상정렬, 다이나믹 프로그래밍을 활용한 문제
• 백준 1005번 문제인 ACM Craft와 풀이방법이 같은 문제이다.

문제 접근 방법

1. 위상 정렬 + DP

• 위상정렬로 작업 순서를 정렬하면서,
• 각 작업을 끝내는 데 걸리는 최소 시간을 spent[] 배열에 저장
• spent[next] = max(spent[next], spent[now] + next.time)으로 갱신

2. 진입차수가 0인 작업부터 시작

• 선행 작업이 없는 작업은 바로 시작 가능 → 큐에 넣기

3. 선행작업이 여러 개일 경우, 가장 오래 걸리는 시간 기준으로 누적

 

https://why-so-chill.tistory.com/96

[백준 1005] ACM Craft (Java) - 위상정렬, 다이나믹 프로그래밍