Course Schedule I
https://neetcode.io/problems/course-schedule
NeetCode
neetcode.io
위상정렬을 사용하여 사이클이 존재하는지 여부를 판단하는 문제다.
차수가 0인 지점을 큐에 넣어 BFS를 돌리고, 다른 지점을 방문할 때마다 차수를 하나씩 빼주고 0이 될때마다 다시 큐에 넣는다.
Course Schedule II
https://neetcode.io/problems/course-schedule-ii
NeetCode
neetcode.io
마찬가지로 위상정렬을 이용하는 문제다. 다른점이 있다면,
Input: numCourses = 3, prerequisites = [[1,0]]
Output: [0,1,2]
이런식으로 주어질 때, 0은 1의 선행과목이 되지만 2는 어떤 과목의 선행과목에도 속하지 않으므로 [0,1,2], [0,2,1] 처럼 0->1 순서만 맞춰주면 된다.
BFS를 돌리면서 차수가 0인 지점부터 리스트에 넣어주면 선행과목부터 순서대로 입력받을 수 있다.