파이썬으로 모든 과목 수강 가능 여부 확인하기

문제 개요

2차원 행렬이 주어졌을 때, matrix[i]는 i번째 과목을 수강하기 위해 먼저 이수해야 하는 선수과목들의 목록을 의미합니다. 이때 주어진 조건 하에서 모든 과목을 수강하는 것이 가능한지 판별하는 프로그램을 작성해야 합니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

matrix = [[1], [2], []]

이 경우 출력은 True입니다. 선수과목이 없는 과목 2부터 수강한 뒤, 과목 1, 마지막으로 과목 0을 수강하면 되기 때문입니다.

핵심 아이디어: 순환(Cycle) 검출

이 문제는 방향 그래프에서 순환이 존재하는지 확인하는 문제와 본질적으로 같습니다. 어떤 과목의 선수과목 관계가 자기 자신에게로 되돌아오는 순환 고리를 형성한다면, 그 사슬에 속한 과목들은 어떤 순서로도 수강할 수 없습니다. 따라서 "모든 과목 수강 가능"과 "그래프에 순환이 없음"은 동치입니다.

이를 DFS(깊이 우선 탐색)로 구현하며, 두 개의 불리언 배열을 사용합니다.

vis[i]: 현재 탐색 경로에서 노드 i를 방문 중인지 표시 (순환 감지용)
chk[i]: 노드 i에서 출발하는 탐색이 이미 안전함이 확인되었는지 표시 (중복 탐색 방지 및 성능 최적화)

알고리즘 단계

dfs(i) 함수를 정의합니다.
vis[i]가 True이면 같은 경로를 다시 방문한 것, 즉 순환이므로 False를 반환합니다.
chk[i]가 True이면 이미 검증이 끝난 노드이므로 즉시 True를 반환합니다.
vis[i]를 True로 설정합니다.
matrix[i]의 각 선수과목 j에 대해 dfs(j)를 재귀 호출하고, 하나라도 False를 반환하면 False를 반환합니다.
탐색을 마치면 vis[i]를 False로 되돌려 경로 표시를 해제하고, chk[i]를 True로 갱신한 뒤 True를 반환합니다.
메인 로직에서는 vis와 chk를 행렬의 행 개수만큼 False로 초기화하고, 모든 노드 i에 대해 dfs(i)를 호출합니다. 하나라도 False가 나오면 False를, 모두 통과하면 True를 반환합니다.

파이썬 구현 예제

class Solution:
   def solve(self, matrix):
      # 방문 여부 및 검증 완료 여부 배열 초기화
      vis = [False for _ in matrix]
      chk = [False for _ in matrix]

      def dfs(i):
         # 현재 경로에서 이미 방문했다면 순환 존재
         if vis[i]:
            return False
         # 이미 안전하다고 확인된 노드라면 생략
         if chk[i]:
            return True
         vis[i] = True
         for j in matrix[i]:
            if not dfs(j):
               return False
         vis[i] = False   # 경로 표시 해제
         chk[i] = True    # 검증 완료 표시
         return True

      for i in range(len(matrix)):
         if not dfs(i):
            return False
      return True

ob = Solution()
matrix = [
   [1],
   [2],
   []
]
print(ob.solve(matrix))

입력

matrix = [
   [1],
   [2],
   []
]

출력

True

동작 원리 상세 설명

위 예제에서 dfs(0)을 호출하면 과목 0의 선수과목인 과목 1로 이동하고, 다시 과목 1의 선수과목인 과목 2로 이동합니다. 과목 2에는 선수과목이 없으므로 탐색이 종료되며, 역방향으로 거슬러 올라가며 각 노드에 chk 표시를 남깁니다.

반면 입력이 [[1], [0], []]처럼 과목 0과 1이 서로를 선수과목으로 요구한다면, DFS 탐색 중 같은 노드를 재방문하게 되어 vis 플래그에 걸리고 False가 반환됩니다. 이것이 순환 검출의 핵심 메커니즘입니다.

복잡도 분석

시간 복잡도: O(V + E). V는 과목(노드) 수, E는 선수과목 관계(간선) 수입니다. chk 배열 덕분에 각 노드와 간선은 최대 한 번씩만 탐색됩니다.
공간 복잡도: O(V). vis, chk 배열과 재귀 호출 스택이 필요합니다.

참고로 이 문제는 위상 정렬(Topological Sort) 알고리즘으로도 해결할 수 있습니다. Kahn 알고리즘이나 DFS 기반 위상 정렬을 적용해 순환 여부를 검사하는 방식 역시 널리 사용되는 대표적인 접근법입니다.

파이썬으로 모든 과목 수강 가능 여부 확인하기 – DFS 순환 검사 알고리즘