[LeetCode] 2050. Parallel Courses III

https://leetcode.com/problems/parallel-courses-iii/description/

Parallel Courses III - LeetCode

문제 유형 : 위상 정렬

문제 난이도 : Hard

 

문제

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCoursej, nextCoursej] denotes that course prevCoursej has to be completed before course nextCoursej (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)th course.

You must find the minimum number of months needed to complete all the courses following these rules:

• You may start taking a course at any time if the prerequisites are met.
• Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

 

n개의 수업과 연결 정보 relation가 주어집니다. [이전코스 ,다음코스]의 형태로 연결성을 가지고 있고, time배열에는 각 코스별 걸리는 시간이 있습니다.

 

수업을 듣기 위해서는, 선수 학습들을 모두 수강하여야 하고, 수업은 동시에 들을 수 있습니다.

이 코스들을 다 듣는 최소 시간을 구하시오.

 

풀이

위상 정렬을 이용하여 풀어주면 된다.

연결 정보로 방향그래프를 만들어주고, 각 노드별로 진입차수를 구해줍니다.

 

진입차수가 0인 수업들부터 큐에 넣습니다.

다음 수업들의 진입차수를 1씩 낮추고, 걸리는 시간의 배열을 업데이트해줍니다.

 

다음 수업 중에서 진입차수가 0이 되는 게 있다면, 큐에 넣어줍니다.

 

마치고 나서, 누적 시간을 담는 배열 중에서 가장 큰 값을 반환합니다.

 

코드

C++

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

		//연결 정보 저장..
        vector<vector<int>> graph(n+1, vector<int>());
        vector<int> indegree(n+1, 0);
        vector<int> distance(n+1, 0);

        for(const auto& relation : relations) {
            graph[relation[0]].push_back(relation[1]);
            indegree[relation[1]]++;
        }

        queue<int> q;
		//진입차수가 0(선수과목이 없는 수업)부터 큐에 삽입
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == 0) q.push(i);
            distance[i] = time[i - 1];
        }
		
        while(!q.empty()) {
            int curr = q.front();
            q.pop();
			//누적 시간 업데이트. 다음 노드들 중에서 선수 과목을 다 들었으면 큐에 넣기.
            for(const auto& next : graph[curr]) {
                distance[next] = max(distance[next], distance[curr] + time[next - 1]);
                indegree[next]--;
                
                if(indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
		//가장 마지막에 끝난 수강 시간 반환
        return *max_element(distance.begin(), distance.end());
    }
};