[Leetcode] 210. Course Schedule II

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

---

총 numCourses 개의 수강해야 하는 강좌가 있으며 0 ~ numCourses-1 의 레이블로 지정되어 있다.

prerequisites[i] = [ai, bi] 로 이루어진 prerequisites 배열이 있다. 이는 ai 강좌를 수강하고 싶은 경우 bi 과정을 먼저 수강해야 함을 의미한다. 모든 강좌들을 마치기 위해 수강해야 하는 강좌의 순서를 구해라. 만일 모든 강좌들을 수강할 수 없다면 빈 배열을 반환해라.

---

adj[i] = i번째 강좌를 수강해야만 들을 수 있는 강좌의 번호들

degree[i] = i번 강좌를 수강하기 위해 수강해야 하는 강좌들의 개수

prerequisites을 탐색하며 위 배열들을 채운다.

degree 배열이 0인 경우 i번 강좌를 수강할 수 있으므로 degree 배열이 0인 i 인덱스를 큐에 넣는다.

큐가 빌때까지 탐색하며 큐의 탑에 있는 강좌번호를 정답 배열에 넣는다. 그리고 adj[강좌번호]에 있는 강좌들의 번호를 인덱스로 가지는 degree 배열의 요소들을 1씩 감소시킨다. 만일 감소한 뒤의 degree 요소값이 0이 되면 해당 인덱스의 강좌도 수강이 가능한 경우이므로 큐에 추가한다.

 

위 과정을 큐가 빌때까지 반복한 뒤 구한 정답 배열의 크기가 numCourses와 같다면 모든 강좌들을 수강할 수 있으므로 정답 배열을 반환하고 다르다면 모든 강좌들을 수강할 수 없는 경우이기 때문에 빈 배열을 반환한다. 

 

N = numCourses, M = |prerequisites|라 할 때, 시간복잡도는 O(N+M).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/210.%20Course%20Schedule%20II.cpp