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 []