[백준] 2056 작업

📌 문제

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

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

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

✔ 접근방법

선후관계가 있는 경우로 위상정렬 알고리즘을 사용하면된다.
생각을 조금 해줘야하는 작업이 끝나는 시간이 있다는 것이다.
선행되는 작업중, 가장 늦게 끝나는 작업의 시간값 + 현재 작업의 시간값이 현재 작업이 끝나는 시간이라는 점을 주의해서 풀이하면 된다.
이 시간 값을 담기 위해 endTime이라는 추가적은 배열을 선언하여 해결하였다.

✔ 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] indegree = new int[n];
		int[] times = new int[n];
		int[] endtime = new int[n];
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		Queue<Integer> qu = new LinkedList<>();

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

		for (int i = 0; i < n; i++) {
			times[i] = sc.nextInt();
			endtime[i] = times[i];
			int num = sc.nextInt();
			indegree[i] = num;
			for (int j = 0; j < num; j++) {
				int first = sc.nextInt() - 1;
				graph.get(first).add(i);
			}
		}

		for (int i = 0; i < n; i++) {
			if (indegree[i] == 0)
				qu.add(i);
		}

		while (!qu.isEmpty()) {
			int target = qu.poll();
			for (int after : graph.get(target)) {
				indegree[after]--;
				endtime[after] = Math.max(endtime[after], endtime[target] + times[after]);
				if (indegree[after] == 0)
					qu.add(after);
			}
		}

		Arrays.sort(endtime);
		System.out.println(endtime[n - 1]);
	}
}

🖋 회고

위상정렬 문제를 몇번 풀어본 경험이 있기 때문에 크게 어려움없이 해결할 수 있었다.
확실히 특정 알고리즘을 이용하여 문제를 풀이한 경험이 있을 경우 문제를 풀이하는 시간도 줄고 반례도 쉽게 찾을 수 있는 것 같다.

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