[LC] 207. Course Schedule

[seungriyou]

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

Approach

Idea 1: Topological Sort

위상 정렬을 수행하며 방문한 노드의 개수와 주어진 numCourses 가 동일한지 판단한다.

동일하다면 주어진 선수과목 순서대로 전체 강의를 수강할 수 있는 것이므로 True를, 아니라면 전체 강의를 수강할 수 없다는 것이므로 False를 반환한다.

Idea 2: DFS w/ 3-state visited 📌

ref:

• https://www.geeksforgeeks.org/detect-cycle-in-a-graph/
• https://leetcode.com/problems/course-schedule/solutions/441722/python-99-time-and-100-space-collection-of-solutions-with-explanation

DFS에서 visited를 사용할 때, 기존에는 0 / 1의 2-state을 사용했었다.

하지만 이번 문제에서는 DFS를 돌며 가능한 모든 path를 탐색하면서 directed graph의 cycle detection을 수행해야하므로, 3-state 으로 기록해야 한다.

• 즉, visited[i]의 값을 다음과 같이 0 / -1 / 1 의 3-state으로 나눌 수 있다.

  visited[i] == 0 : 아직 방문 X
  visited[i] == -1 : 지금 방문 중 (즉, 현재 보고 있는 path에 포함)
  visited[i] == 1 : 이미 방문 완료

• 혹은, current_path(visited[i] == -1에 해당)와 visited(visited[i] == 1에 해당)라는 set()으로 관리해도 된다.

[!important] visited를 3-state으로 기록할 수 있다!

정리: https://seungriyou.github.io/posts/undirected-and-directed-graph-cycle-detection/

Complexity

• Time: O(v+e) (모든 간선과 노드를 한 번씩 방문)
• Space: O(v+e) (adjacency list) (ref)