2050. Parallel Courses III

• 수업 별로 시간 및 의존 관계가 존재할 때 가장 짧은 시간에 모든 수업을 완료할 수 있는 경우를 찾는 문제.
• 수업은 노드로 표현되며 의존 관계는 그래프의 선으로 표현된다.

• 의존 관계를 인접 리스트로 구성하되 방향을 반대로 한다.

• 모든 노드 중 루트 노드 (마지막 수업)를 구하고 각 루트 노드별로 탐색하여 총 수업을 듣는데 필요한 시간을 구하여 map dp에 저장한다.

• 모든 경로 중 가장 큰 값이 모든 수업을 완료하는데 드는 시간이다.

class Solution {
public:
    void traverse(map<int,vector<int>>& adj, vector<int>& time, map<int,int>& dp, int i, int prev) {
        int nTime = prev + time[i-1];
        if (nTime < dp[i]) return;
        dp[i] = nTime;
        for (auto& j : adj[i]) {
            traverse(adj, time, dp, j, nTime);
        }
    }
    
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        map<int,vector<int>> adj;
        set<int> leaf;
        for (int i = 1; i <= n; ++i) {
            leaf.insert(i);
        }
        for (auto& e : relations) {
            adj[e[1]].push_back(e[0]);
            leaf.erase(e[0]);
        }
        map<int,int> dp;
        int result = 0;
        for (auto i : leaf) {
            traverse(adj, time, dp, i, 0);
        }
        for (auto entry : dp) {
            result = max(result, entry.second);
        }
        return result;
    }
};