커리큘럼

 

문제

특정 수업을 듣고 싶을 때, 이 과목을 수강하기 위한 선수과목이 존재할 수 있다. 따라서 특정 수업을 듣기 위해서는 해당 선수과목을 수강한 후 수강이 가능하다.

0번 과목부터 N번 과목까지 수강 소요 시간, 선수과목 인덱스가 주어질 때, 모든 과목을 듣는데 각각 필요한 최소시간을 구하라.

 

 

로직

예를 들어 데이터가 다음과 같이 주어졌다고 가정하자.

 

data

10

10, 1

4, 1

4, 3, 1

3, 3

즉, 0번과목을 듣기 위해서는 10시간이 필요하고 선수과목은 없다. 또한 1번 과목을 듣기위해서는 0(1-1)번 과목을 선수강해야하고 소요시간은 10시간이 소요된다.

 

1. 인접행렬을 만든다.

- 특정 과목을 듣고 다음에 들을 수 있는 과목을 체크함을 위함.(특정 과목의 인접행렬에 들어간 인덱스는 이 특정과목을 선수과목으로 하는 과목들임.)

아래 값들은 특정 인덱스를 선수과목으로 하는 과목들임.

0 : [1, 2, 3]

1 : []

2 : [3, 4]

3 : []

4 : []

 

2. 진입 차수를 만든다.

- 특정 노드에 대해서 특정 노드를 수강하기 위해 수강해야할 선수과목의 수

- 0번과목을 듣기위해서 선수과목 없음, 1번과목을 듣기 위해서는 0번 과목을 들어야 함 따라서 count=1

0 : 0

1 : 1

2 : 1

3 : 2

4 : 1

 

3. 각 수업별 걸리는 시간 초기화

 

4. 진입차수가 0인 과목부터 시작(큐에 넣는다.)

 

5. 해당 과목을 선수과목으로 하는 과목들을 체크

해당 과목을 선수과목으로 한다면? 

5-1. 진입 차수 -= 1

 

6. 진입 차수가 0이된다면?

6-1. 지금 체크하는 과목(큐에서 꺼낸)의 소요시간 + 현재 진입 차수가 0이된 과목의 소요시간

6-2. 큐에 넣는다.

 

 

코드

import java.util.*;
public class Question3 {
    public static void main(String[] args){
        int[][] data = {
            {10, -1}, {10, 1, -1}, {4, 1, -1},
            {4, 3, 1, -1}, {3, 3, -1}
        };
        List<List<Integer>> map = new ArrayList<>();
        List<Integer> time = new ArrayList<>();
        int[] indegree = new int[5];

        for(int i=0; i<5; i++){
            indegree[i] = 0;
        }
        for(int j=0; j<data.length; j++){
            List<Integer> now = new ArrayList<>();
            map.add(now);
            for(int i=1; i<data[j].length-1; i++){
                map.get(data[j][i]-1).add(j);
                indegree[j] += 1;
            }
            time.add(data[j][0]);
        }
        List<Integer> queue = new ArrayList<>();
        for(int i=0; i<indegree.length; i++){
            if(indegree[i] == 0){
                queue.add(i);
                break;
            }
        }
        while(!queue.isEmpty()){
            int now = queue.remove(0);
            for(int i : map.get(now)){
                indegree[i] -= 1;
                if(indegree[i] == 0){
                    queue.add(i);
                    time.set(i, time.get(i)+time.get(now));
                }
            }
        }
    }
}