[LeetCode] 1462. Course Schedule IV

https://leetcode.com/problems/course-schedule-iv/description/

leetcode - Course Schedule IV

문제 유형: 그래프, 위상 정렬, 플로이드 위셜, 최단 거리

문제 난이도: Medium

 

문제

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.

• For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.

Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.

You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.

Return a boolean array answer, where answer[j] is the answer to the jth query.

 

numCourses개의 들어야 하는 수업들이 있습니다. 0부터 numCourses-1번까지 번호가 붙습니다. prerequisites[i] = [ai, bi]는 ai를 bi보다 먼저 들어야 한다는 의미입니다.

이 관계는 직접적이지 않을 수 있습니다.

연쇄된 관계도 인정됩니다.

queries[j] = [uj, vj]에 대해서 uj가 vj의 선수과목인지 에 대한 정보들을 answer배열에 순차적으로 담아서 반환하시오.

 

풀이

물론 위상정렬을 이용할 수도 있겠지만..

 

플로이드-워셜을 응용하여 모든 노드들간의 관계를 구성할 수 있다.

처음에는 자기자신과 prerequisites배열의 정보로 인접행렬을 구성한다.

경유가능한 노드번호 k를 0부터 numCouses까지 하는동안,

adj[i][k] 와 adj[k][j]가 모두 true라면, adj[i][j]는 true이다.

 

이제, 각 쿼리 u, v에 대해 adj[u][v]의 값들을 담아서 리턴하면 된다.

 

코드

C++

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        // variation of floyd-warshall
        vector<vector<bool>> adj(numCourses, vector<bool>(numCourses));
        for(int i = 0; i < numCourses; ++i) adj[i][i] = true;
        for(const auto &elem : prerequisites) {
            int u = elem[0];
            int v = elem[1];
            adj[u][v] = true;
        }

        for(int k = 0; k < numCourses; ++k) {
            for(int i = 0; i < numCourses; ++i) {
                for(int j = 0; j < numCourses; ++j) {
                    if(adj[i][k] && adj[k][j]) adj[i][j] = true;
                }
            }
        }

        vector<bool> ans;
        for(const auto &query : queries) {
            int u = query[0];
            int v = query[1];
            ans.push_back(adj[u][v]);
        }
        return ans;
    }
};