[leetcode][207] Course Schedule

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

---

numCourses 개의 코스가 있다. 이 코스들은 선행되는 코스들이 있을 수 있다.

선행되는 코스들을 모두 수강한 경우, 해당 코스를 수강할 수 있다.

코스들의 개수(numCourses), 선행 코스들에 대한 정보(prerequisites)가 주어질 때, 모든 코스들을 수강할 수 있는지 구해라.

---

위상정렬(topological sort) 관련 문제다.

 

1. 코스를 선수 과목으로 보는 코스들의 번호를 저장하는 2차원 배열. 

2. 코스를 수강하기 위해 선행되어야 하는 코스의 수를 저장하는 1차원 배열.

3. 남은 선수 코스의 개수가 0이여서 수강할 수 있는 코스를 저장하는 큐.

총 3개의 자료구조를 사용했다.

 

먼저 선수 과목의 정보를 모두 탐색하면서 1, 2번 배열을 저장한다.

배열들을 만들었으면 2번 배열을 탐색하면서 선행 코스의 수가 0개인(바로 수강 가능) 코스 번호를 3번 큐에 저장한다.

큐를 탐색하면서 탐색한 코스들의 수를 저장한다. 탐색 시 1번 배열을 보고 해당 과목을 선수 코스로 보는 코스들의 번호를 가져올 수 있고 이를 인덱스로 가지는 2번 배열의 요소를 -1 해준다.(선행 코스의 개수가 1개 줄었으므로)

2번 배열을 갱신하면서 0이 되는 경우 큐에 넣어준다.

큐가 빌 때 까지 위 과정을 반복하고, 큐가 비었을 때, 탐색한 코스들의 수가 총 코스의 개수와 같다면 true, 다르다면 false를 반환한다.

 

시간복잡도는 O(V+E). (V: 정점, E: 간선) 즉, O(numCourses + |prerequisites|)이다.

---

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