Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 해결하는 코스 일정(Course Schedule) 문제: DFS 사이클 검출

문제 개요

총 numCourses개의 강좌를 수강해야 하며, 각 강좌에는 0부터 numCourses-1까지 번호가 붙어 있다고 가정해 봅시다. 일부 강좌는 선수 과목이 있을 수 있습니다. 예를 들어 강좌 0을 듣기 위해서는 먼저 강좌 1을 이수해야 한다는 조건은 [0, 1] 쌍으로 표현됩니다. 이때 전체 강좌 수와 선수 과목 쌍의 목록이 주어졌을 때, 모든 강좌를 이수하는 것이 가능한지 판별해야 합니다.

예를 들어 입력이 numCourses = 2, prerequisites = [[1, 0]]이라면 결과는 true입니다. 총 2개의 강좌가 있으며, 강좌 1을 수강하려면 강좌 0을 먼저 이수해야 합니다. 이 조건은 충분히 만족할 수 있으므로 모든 강좌 수강이 가능합니다.

해결 전략

이 문제는 선수 과목 관계를 방향 그래프(directed graph)로 모델링한 뒤, 그래프에 사이클(cycle)이 존재하는지 확인하는 방식으로 풀 수 있습니다. 사이클이 있다면 강좌들 사이에 순환 의존 관계가 생겨 어느 강좌도 먼저 들을 수 없게 되므로, 모든 강좌 이수는 불가능합니다.

단계별 알고리즘은 다음과 같습니다.

  • 메인 메서드(canFinish)에서 numCourses와 prerequisites를 입력받습니다.
  • prerequisites 목록이 비어 있다면 즉시 true를 반환합니다.
  • 길이가 numCourses인 visited 배열을 생성하고 0으로 초기화합니다. (0: 미방문, -1: 탐색 중, 1: 탐색 완료)
  • make_graph 메서드를 통해 prerequisites를 기반으로 인접 리스트(adjacency list) 형태의 그래프를 생성합니다.
  • i를 0부터 numCourses-1까지 반복하면서, 아직 방문하지 않은 노드라면 DFS 기반의 cycle 메서드를 호출해 사이클 여부를 검사합니다.
  • 사이클이 하나라도 발견되면 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]]))

핵심 로직 설명

cycle 메서드는 깊이 우선 탐색(DFS)을 활용해 사이클을 검출합니다. 현재 노드의 상태 값이 -1이라면 아직 탐색이 진행 중인 노드를 다시 만난 것이므로 사이클이 존재한다는 의미로 false를 반환합니다. 상태 값이 1이라면 이미 탐색이 완료된 노드이므로 더 이상 확인할 필요 없이 true를 반환합니다. 탐색이 정상적으로 끝나면 상태 값을 1로 갱신하여 중복 탐색을 방지합니다. make_graph 메서드는 각 선수 과목 쌍 [a, b]에서 b를 키로, a를 값으로 저장하여 'b를 이수해야 a를 들을 수 있다'는 방향 그래프를 인접 리스트로 구성합니다.

입력

2
[[1,0]]

출력

true