Topological Sort_Course Schedudle

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1: Input : numCourses = 2, prerequisites = [[1,0]] Output : true Explanation : There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2: Input : numCourses = 2, prerequisites = [[1,0],[0,1]] Output : false Explanation : There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Example 3: Input : [[1,0],[2,1],[3,2]] Output : true

자료구조 : 1차원 배열, 큐

알고리즘 1. 과목 수만큼 크기의 1차원 배열(inDegree)을 생성하여 초기 값을 0으로 셋팅한다. 2. '0'인 것(마지막 과목)을 큐에 넣는다. 3. 큐와 1차원 배열을 왔다갔다 하며 수업 선이수 과정이 acyclic인지 backtracking한다. 0->1->2->3 일 때, 0->1 : 1개, 1->2 : 1개, 2->3 : 1개 여야한다. 마지막 과목(3)에서 백트랙킹하여 앞의 코스 수를 감산하여 0으로 만든다.

큐에서 노드(=코스를 의미)를 꺼내온다. (course) 2차원 배열(nums)에서 course(nums[ i ][0]를 찾고, course 선 이수과정(nums[ i ][1])을 inDegree에서 감산한다. inDegree에서 감산한 nums[ i ][1](=코스)이 0이면, 0이 된 코스를 큐에 다시 넣는다. 4. 1차원 배열의 모든 원소가 0이면 참이 되며 true를 리턴한다.