문제

수행해야 할 작업 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)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

출력

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

풀이

위상정렬을 사용하여 문제를 해결하면 된다.

위상정렬을 수행하면서 각 노드에 대하여 인접한 노드를 확인할 때, 인접한 노드에 대하여 현재보다 강의 시간이 더 긴 경우를 찾는다면, 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 result 테이블을 갱신한다.

이와 같은 공식을 사용하는 이유는 이전에 모든 작업이 끝나지 않으면 다음 작업을 수행할 수 없기 때문에 계속적으로 최대 시간을 구하는 것이다.

예를들어, A=30 시간 B=20 시간 C=40시간이 주어지고 C 작업을 수행하기 위해 A와 B작업이 선행되어야 한다고 가정하자. 이때 C 작업을 수행하기 위해서는 최소 70시간이 필요하다.

처음 결과를 출력할 때 result[N]에 대해서만 출력했으나 오답처리가 되었다. 생각해보니 모든 작업을 완료하는 과정에서 더 오래걸리는 시간이 존재할 수 있다. 따라서 결과를 출력할 때 result 테이블에서 제일 오래걸린 시간을 출력하면 된다.

소스

import java.util.*;

public class Main {
	public static int n;
	public static int[] indegree = new int[10001];

	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	public static int[] times = new int[10001];

	public static void topologySort() {
		int[] result = new int[10001];

		for (int i = 1; i <= n; i++) {
			result[i] = times[i];
		}

		Queue<Integer> q = new LinkedList<Integer>();

		for (int i = 1; i <= n; i++) {
			if (indegree[i] == 0) {
				q.offer(i);
			}
		}

		while (!q.isEmpty()) {
			int now = q.poll();
			for (int i = 0; i < graph.get(now).size(); i++) {

				// 인접한 노드에 대하여 더 오랜 시간이 걸리는 경위의 시간 값을 저장
				result[graph.get(now).get(i)] = Math.max(result[graph.get(now).get(i)],
						result[now] + times[graph.get(now).get(i)]);
				indegree[graph.get(now).get(i)] -= 1;

				if (indegree[graph.get(now).get(i)] == 0) {
					q.offer(graph.get(now).get(i));
				}
			}
		}

		// 결과 출력
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			ans = Math.max(ans, result[i]);
		}

		System.out.println(ans);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();

		// graph 초기화
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<Integer>());
		}

		// 1~N 번 작업
		for (int i = 1; i <= n; i++) {
			int time = sc.nextInt();
			times[i] = time;
			// x : 작업의 개수
			int x = sc.nextInt();
			for (int j = 0; j < x; j++) {
				// job : 선행 관계 있는 작업
				int job = sc.nextInt();
				indegree[i] += 1;
				graph.get(job).add(i);
			}
		}

		topologySort();
	}

}