이코테 - 커리큘럼 with JAVA

 

 

해결

기본적으로는 위상정렬 알고리즘을 사용한다.

하지만, 주의할 점은 다음 노드를 방문할 때이다.

예를 들어, 3번 과목은 1, 2번 과목을 선수행해야하고 2번은 1번과목을 선수행해야한다고 가정하자.

이 때, 3번과목의 비용은 (2번과목까지 선수행 비용 + 3번 비용) vs (1번과목까지 선수행 비용 + 3번 비용) 중 큰 것으로 매겨진다.

 

 

 

 

 

코드

import java.util.*;

// 커리 큘럼
public class Practice3 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] graph = new int[n];
        int[] times = new int[n];
        List<List<Integer>> classes = new ArrayList<>();
        for(int i=0; i<n; i++){
            classes.add(new ArrayList<>());
        }
        for(int i=0; i<n; i++){
            times[i] = sc.nextInt();
            while(true){
                int before = sc.nextInt();
                if(before == -1){
                    break;
                }
                graph[i] += 1;
                classes.get(before-1).add(i);
            }
        }
        List<Integer> queue = new ArrayList<>();
        for(int i=0; i<n; i++){
            if(graph[i] == 0){
                queue.add(i);
            }
        }
        int[] result = new int[n];
        for(int i=0; i<n; i++){
            result[i] = times[i];
        }
        while(queue.size() > 0){
            int now = queue.remove(0);
            for(int next : classes.get(now)){
                // 그전에 방문한 내역 vs now까지 오는데 걸리는 비용 + next의 비용
                result[next] = Math.max(result[next], result[now]+times[next]);
                graph[next] -= 1;
                if(graph[next] == 0){
                    queue.add(next);
                }
            }
        }
        for(int i=0; i<n; i++){
            System.out.println(result[i]);
        }
    }
}