leetcode medium : Course Schedule (Grind 75 Graph문제 4)

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

Course Schedule - LeetCode

 

무슨 문제인지 아는 사람은 보고 아하 하고 웃고

모르는 사람은 보고 머리 쥐어짜매는 문제

 

이건 directed graph에서 cycle을 찾는 문제,

정확히 말하면 위상정렬(topology sort) 문제다.

 

위상정렬은 문제의 예시처럼 선후 관계가 directed edge로 표현된 directed graph가 있을때 선후관계를 해치지 않도록 노드를 나열하는 정렬방법이다. 예를 들어 A -> C, B -> C라면 C는 A와 B가 방문되기 전에는 방문될 수 없는 노드이므로 [A, B, C] 혹은 [B, A, C] 순서로 방문해야 선후관계를 위반하지 않고 방문이 가능하다. 이게 위상정렬이다.

 

위상정렬의 핵심은 indegree다.

노드의 indegree는 그 노드로 들어오는 edge의 개수를 말한다.

위 예시에서 C의 indegree는 2고 A랑 B는 0이다.

indegree가 0인 노드들은 선수 노드가 없으므로 가장 먼저 방문해도 되는 노드들이다.

이것들부터 방문하면서 연결된 노드들의 indegree를 1씩 깎아주고 0이 되는 노드가 있으면 다음 방문 장소로 지정한다.

사이클이 없는한, 전부다 방문하고 나면 모든 노드의 indegree가 0이 되어야 한다.

 

BFS

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]

        indegree = [0] * numCourses

        for src, dst in prerequisites:
            graph[src].append(dst)
            indegree[dst] += 1

        result = []
        q = deque()

        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)

        while q:
            now = q.popleft()
            result.append(now)
            for i in graph[now]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    q.append(i)
    
        return sum(indegree) == 0

 

DFS

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]

        indegree = [0] * numCourses

        for src, dst in prerequisites:
            graph[src].append(dst)
            indegree[dst] += 1

        def dfs(node):
            indegree[node] = -1
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    dfs(nxt)
        
        for i in range(numCourses):
            if indegree[i] == 0:
                dfs(i)

        return sum(indegree) == -numCourses