[Leetcode] 210. Course Schedule II - Topological Sorting

1. 문제링크

https://leetcode.com/problems/course-schedule-ii/

Course Schedule II - LeetCode

a과목의 선수과목이 b일 때 vector = {a, b};로 표시한다.

n개의 과목을 학습해야하는 경우, 수강하는 과목의 순서를 return한다.

만약 prerequisites가 잘못 구성되어 있다면 empty 배열을 반환한다.

prerequisites를 줄여서 pre라고 표현하겠음

 

 

 

2. 데이터를 정리하자 - map. vector, queue 사용

- numCourse = 4

- pre = [[1,0], [2,0], [3,1], [3,2]] 라면

위와 같이 표현할 수 있다.

 

들어오는 화살표의 갯수를 vector에 저장하고

선수과목에서 이어지는 과목들을 모두 map에 저장해둔다.

 

1) 들어오는 화살표의 갯수 카운트

vector<int> in(n);

in[0] = 0, in[1] = 1, in[2] = 1, in[3] = 2

 

2) 선수과목과 연결되는 과목을 map에 저장

m[0] = {1, 2};

m[1] = {3};

m[2] = {3};

m[3] = {};

 

3) 선수과목이 없는 과목은 queue에 push한다

현재 in배열에서 값이 0인건 첫번째 인덱스인 0번 과목이다.

0의 선수과목이 없으므로 queue에 넣어준다.

만약 1)에서 값이 0인 데이터가 없다면 이건 cycle이 되므로 잘못된 pre인 것임 ㅇㅇ empty 배열 반환 ㄱ

 

4) queue에 데이터가 없어질 때 까지 map을 돌쟈

q에는 뭐가 들어있다? 선수과목이 업는 과목만 들어있다.

그러니 결과배열에 push해둔다.

그 과목과 연결되는 과목들을 map에서 찾아서 in 화살표의 값을 하나씩 제거해준다.

만약 in화살표가 0이 되면 다시 queue에 넣어준다

 

5) 결과 vector의 사이즈가 n이 되어야한다

만약 결과벡터의 사이즈가 n이 아니라면 이것도 pre가 잘못된 것이다

잘못된건 모다? empty 배열을 반환한다

 

 

 

3. solution

class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& pre) {
        map<int, vector<int>> m;
        vector<int> in(n);
        for(auto v : pre){
            m[v[1]].push_back(v[0]);
            in[v[0]]++;
        }

        queue<int> q;
        for(int i = 0; i < n; i++){
            if(in[i] == 0)
                q.push(i);
        }
        

        vector<int> res;
        while(!q.empty()){
            int curr = q.front();
            q.pop();
            res.push_back(curr);
            for(auto i : m[curr]){
                in[i]--;
                if(in[i] == 0)
                    q.push(i);
            }
        }
        if(res.size() == n)
            return res;
        
        return {};
    }
};