[LeetCode][Python3] 210. Course Schedule II

Problem :

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

My Solution :

class Solution:

def findOrder(self, numCourses, prerequisites):

def dfs(vertex):

if visited[vertex]:

return True

if visited[vertex] == False:

return False

visited[vertex] = False

for prerequisite in graph[vertex]:

if not dfs(prerequisite):

return False

courses_order.append(vertex)

visited[vertex] = True

return True

visited = [None]*numCourses

graph = [[] for _ in range(numCourses)]

courses_order = []

for vertex, prerequisite in prerequisites:

graph[vertex].append(prerequisite)

for vertex in range(numCourses):

if not dfs(vertex):

return []

return courses_order

Comment :

지난번에 아래 문제를 DFS로 풀었기 때문에 코드 몇줄만 수정해서 풀었다.

2019/03/31 - [프로그래밍/LeetCode] - [LeetCode][Python3] 207. Course Schedule

그리고 아래는 위상 정렬을 이용한 풀이 방법

My Solution 2 :

from collections import deque

class Solution:

def findOrder(self, numCourses, prerequisites):

graph = {}

indegree = {}

courses_order = []

for vertex, prerequisite in prerequisites:

graph.setdefault(prerequisite, []).append(vertex)

indegree[vertex] = indegree.get(vertex, 0) + 1

queue = deque(v for v in range(numCourses) if v not in indegree)

while queue:

vertex = queue.popleft()

courses_order.append(vertex)

for neighbor in graph.get(vertex, []):

indegree[neighbor] -= 1

if indegree[neighbor] == 0:

queue.append(neighbor)

return courses_order if len(courses_order) == numCourses else []