파이썬 코스 일정

0에서 numCourses-1까지 레이블이 지정된 총 numCourses 코스가 있다고 가정합니다. 일부 코스에는 전제 조건이 있을 수 있습니다. 예를 들어 코스 0을 수강하려면 먼저 [0,1] 쌍을 사용하여 표현되는 코스 1을 수강해야 합니다. 제공되는 총 과정의 수와 전제 조건 쌍 목록이 있다고 가정하면 모든 과정을 완료할 수 있는지 확인해야 합니다.

따라서 입력이 − numCourses =2이고 전제 조건 =[[1, 0]]인 경우 총 2개의 코스가 있기 때문에 결과는 true가 됩니다. 코스 1을 수강하려면 코스 0을 완료해야 합니다. 그래서 가능합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 기본 방법에서는 numCourses와 전제 조건이 필요합니다. 이것은 다음과 같이 작동합니다. -

• 전제 조건에 항목이 없으면 true를 반환합니다.

• 방문이라는 배열을 만들고 0으로 채우고 범위는 numCourses와 동일합니다.

• adj_list :=전제 조건을 사용하여 그래프 생성

• 0 ~ numCourses

  범위의 i에 대해

  • 방문[i]이 거짓이면

    • 그래프에서 방문한 노드 사이에 주기가 없으면 false를 반환합니다.

• true를 반환

예

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def canFinish(self, numCourses, prerequisites):
      if len(prerequisites) == 0:
         return True
      visited = [0 for i in range(numCourses)]
      adj_list = self.make_graph(prerequisites)
      for i in range(numCourses):
         if not visited[i]:
            if not self.cycle(adj_list,visited,i):
               return False
      return True
   def cycle(self,adj_list,visited,current_node = 0):
      if visited[current_node] ==-1:
         return False
      if visited[current_node] == 1:
         return True
      visited[current_node] = -1
      if(current_node in adj_list):
         for i in adj_list[current_node]:
            if not self.cycle(adj_list,visited,i):
               return False
      visited[current_node] = 1
      return True
   def make_graph(self,array):
      adj_list = {}
      for i in array:
         if i[1] in adj_list:
            adj_list[i[1]].append(i[0])
         else:
            adj_list[i[1]] = [i[0]]
      return adj_list
ob = Solution()
print(ob.canFinish(2, [[1,0]]))

입력

2
[[1,0]]

출력

true