문제 이해

선행 작업이 모두 완료되어야만 이후 작업을 수행할 수 있다.
이 때, K작업의 선행 작업은 1 ~ (K-1) 작업 중에 존재한다.

모든 작업을 완료하기 위해 필요한 최소 시간을 구하는 문제이다.

---

문제 풀이

선행 작업이 존재한다는 것은 그래프로 표현했을 때 방향성이 존재한다는 의미이다.
특히, K 작업의 선행 작업이 1 ~ K-1 작업 중에 존재한다면, Cycle은 절대로 존재할 수 없다.
하지만, 이 문제는 DAG라고 하더라도 굳이 위상정렬로 풀 필요가 없다.

바로 "1 ~ (K-1) 작업 중에 존재한다"라는 문구 때문이다.

작업 1 ~ N까지 순차대로 작업 시간을 구하면, Math.max() 명령을 통해 손쉽게 전체 작업 시간을 알 수 있으며, 이 중 최댓값의 작업 종료 시간을 가진 작업이 끝나면 모든 작업이 종료될 것이다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static ArrayList<Integer>[] edges;
	static int[] cost;
	static int[] answer;
	
	static void sort() {
		for(int i =1;i<N+1;i++) {
			answer[i]+=cost[i]; 
            // i의 선행 작업이 모두 끝난 시간이 현재 answer[i]에 저장되어 있다.
            // 따라서, cost[i]를 더하면 i의 선행 작업을 끝나고 i를 끝낼 때까지 
            // 걸린 시간이 나올 것이다.
			for(int s:edges[i]) {
				answer[s] = Math.max(answer[i], answer[s]);
                // i -> tmp의 순서 관계를 가진다.
                // answer[s]에는 여러 i 중 가장 오래 걸린 선행 작업 시간이 
                // 저장되어야 하므로,
                // Math.max()를 통해 가장 긴 선행 작업 시간이 저장되도록 한다.
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		edges = new ArrayList[N+1];
		cost = new int[N+1];
		answer = new int[N+1];
		
		for(int i =1;i<N+1;i++) {
			edges[i] = new ArrayList<>();
		}
		
		for(int i =1;i<N+1;i++) {
			int tmp_cost = sc.nextInt();
			cost[i] = tmp_cost;
			
			int rec = sc.nextInt();
			for(int j =0;j<rec;j++) {
				int tmp = sc.nextInt();
				edges[tmp].add(i); 
                // tmp작업을 끝내야만 i 작업을 시작할 가능성이 생긴다.
                // 즉, 화살표 방향은 tmp -> i이다.
			}
		}
		
		sort();
		
		int ans_max = Integer.MIN_VALUE;
		
		for(int i =1;i<N+1;i++) {
			ans_max = Math.max(ans_max, answer[i]);
		}
		System.out.println(ans_max);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2,3,4번째 줄 틀렸습니다 : 굳이 위상정렬을 활용하려 하다가 틀렸다. 먼저 위상정렬을 사용했을 때 틀린 이유는, 내가 위상정렬을 통해 구현한 알고리즘은 특정 상황에 대한 처리가 불가했다. 자세히는 연결 요소가 하나가 아니고, 연결 요소가 여러 개인 경우의 처리가 불가능했다. 물론, visit 배열을 활용하여 위상 정렬을 통해서도 문제를 해결할 수도 있었겠지만, 내가 위에서 설명한 방법을 통해 조금 더 쉽고 직관적으로 구현할 수 있어 풀이 방법을 바꿔 정답을 맞췄다.