[백준] 2056 작업 (java)

1. 문제

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

2. 풀이

키워드: 위상정렬

(위상 정렬에 대해서는 이 블로그를 참고하자)

 

- 위상정렬의 핵심은 아래 네가지 변수를 잘 선언하는 것이다. (위 블로그 참조)

- 이 문제에서는 같은 순서(같은 선행조건을 가진)의 작업이라면 동시에 실행된다고 했다. 또 모든 작업을 완료 해야하기 때문에 동시에 실행되는 작업에서는 결국 가장 오래 수행되어야 하는 작업의 시간을 더해야한다. 

3. 소스코드

package org.hanghae;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BG_작업 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st;
    int n = Integer.parseInt(br.readLine());

    ArrayList<ArrayList<Integer>> array = new ArrayList<>();
    for(int i = 0; i <= n; i++){
      array.add(new ArrayList<>());
    }

    int[] indegree = new int[n + 1];
    int[] time = new int[n + 1];

    for(int i = 1; i <= n; i++) {
      st = new StringTokenizer(br.readLine());

      time[i] = Integer.parseInt(st.nextToken()); // 몇 시간이 걸리는지
      int num = Integer.parseInt(st.nextToken()); // 몇개의 선행 작업이 필요한지

      for(int j = 0; j < num; j++) { // 필요한 선행작업만큼 반복문
        int temp = Integer.parseInt(st.nextToken()); // 선행작업의 번호 나는 0부터 시작하므로 여기서 -1 해야함
        array.get(temp).add(i); // 그 선행작업들에게 현재 작업번호를 추가함

        indegree[i]++;
      }
    }

    bw.write(topologicalSort(n, array, indegree, time) + "\n");
    bw.flush();
    bw.close();
    br.close();
  }

  private static int topologicalSort(int n, ArrayList<ArrayList<Integer>> a, int[] indegree, int[] time) {
    Queue<Integer> q = new LinkedList<>();

    int[] result = new int[n+1];
    for(int i = 1; i <= n; i++) {
      result[i] = time[i];

      // indegree 가 0 인 작업을 큐에 넣는다.
      if(indegree[i] == 0) {
        q.offer(i);
      }
    }

    while(!q.isEmpty()) {
      int now = q.poll(); // 현재 작업

      for(int next : a.get(now)) {
        indegree[next]--;

        result[next] = Math.max(result[next], result[now] + time[next]);

        // 새롭게 indegree 가 0 이 된 작업을 큐에 넣음
        if(indegree[next] == 0){
          q.offer(next);
        }
      }
    }

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

}