[LC] 210. Course Schedule II

[seungriyou]

<210. Course Schedule II>

Approach

[Blog 정리글] directed graph의 cycle detection 관련 문제

Idea 1: Topological Sort (BFS)

indegree 배열을 이용한 위상 정렬 문제로 풀 수 있다.

다음과 같이 directed graph와 indegree 배열을 생성한다.

# create graph & indegree array
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for e, s in prerequisites:
    graph[s].append(e)
    indegree[e] += 1

indegree[npos] == 0인 원소를 deque에 넣으며 BFS로 순회한다.

q = deque(i for i, ind in enumerate(indegree) if ind == 0)
res = []

# topological sort
while q:
    pos = q.popleft()
    res.append(pos)

    for npos in graph[pos]:
        indegree[npos] -= 1
        if indegree[npos] == 0:
            q.append(npos)

BFS 후, 정렬 과정에서 모은 course의 개수가 전체 course의 개수와 다르다면 전체 course를 들을 수 없는 것(= cycle이 존재)이므로 []을 반환해야 함에 주의한다.

# if impossible to finish all courses, return empty array
return res if len(res) == numCourses else []

Idea 2: 3-State DFS

다음과 같이 세 가지 상태를 가지는 DFS를 사용한다.

visited 값	의미
0	아직 방문 X
1	이미 방문 O
-1	현재 보고 있는 path에 존재 (➡️ 마주치면 cycle 발생)

directed graph와 DFS를 위한 visited 배열을 생성한다.

# create graph & indegree array
graph = [[] for _ in range(numCourses)]
visited = [False] * numCourses
for e, s in prerequisites:
    graph[s].append(e)

DFS 로직의 주요 사항은 다음과 같다.

• base condition

  1. visited[pos] == -1 이라면, cycle이 발생한 것이므로 False를 반환한다.
  2. visited[pos] == 1 이라면, 이전에 방문했던 곳이므로 더이상 해당 위치로 방문하지 않고 다음으로 넘어가기 위해 True를 반환한다.

• recursion

  1. 현재 pos를 현재 path에서 보고 있다고 표시하기 위해 visited[pos] = -1로 설정한다.
  2. 이웃을 순회하며 dfs(npos)를 수행한다. 이때, 해당 결과에서 cycle이 발생했다면 False를 반환한다.
  3. 문제 없이 이웃을 순회했다면 현재 pos를 방문했다고 표시하기 위해 visited[pos] = 1로 설정한다.

• record: 현재 pos를 방문 완료했으니 res에 모은다.

res = []

def dfs(pos):
    # base condition
    # (1) cycle 발생 시 False 반환
    if visited[pos] == -1:
        return False
    # (2) 이전에 방문했던 곳이라면 더이상 방문 X, True 반환
    if visited[pos] == 1:
        return True

    # recur
    visited[pos] = -1   # 현재 pos를 보고있다고 표시
    for npos in graph[pos]:
        # 다음 위치인 npos에서 cycle이 발생한다면 False 반환
        if not dfs(npos):
            return False
    visited[pos] = 1    # 현재 pos를 방문했다고 표시

    # record
    res.append(pos)

    return True

모든 노드에서 dfs()를 수행하여 cycle이 발생하는 경우가 있다면 []를 반환하고, 그게 아니라면 res를 뒤집어서 반환한다. (recursive 하므로 순서가 반대로 기록되게 된다)

for i in range(numCourses):
    # i에서부터 시작해서 cycle이 발생한다면 전체 course를 들을 수 없으므로 [] 반환
    if not dfs(i):
        return []

return res[::-1]

Complexity

• Time: O(N + E) (adjacency list = O(E), DFS/BFS = O(N + E))
• Space: O(N + E)