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

파이썬으로 푸는 병렬 과목(Parallel Courses) 문제: 위상 정렬로 최소 학기 수 구하기

N개의 과목이 있으며, 각 과목에는 1부터 N까지 번호가 붙어 있다고 가정해 보겠습니다. 또한 선수 관계를 담은 relations 배열이 주어지는데, relations[i] = [X, Y]는 과목 X와 Y 사이의 선수 관계를 나타냅니다. 다시 말해, 과목 Y를 수강하려면 반드시 먼저 과목 X를 이수해야 합니다.

한 학기에는 수강하려는 과목의 선수과목을 모두 이수한 상태라면 여러 과목을 동시에 수강할 수 있습니다. 우리가 구해야 할 값은 모든 과목을 이수하는 데 필요한 최소 학기 수입니다. 만약 어떤 방법으로도 모든 과목을 이수할 수 없다면 -1을 반환해야 합니다.

예를 들어 입력이 N = 3, relations = [[1,3],[2,3]]이라면 출력은 2가 됩니다. 첫 번째 학기에 과목 1과 2를 동시에 수강하고, 두 번째 학기에 과목 3을 수강하면 되기 때문입니다.

접근 방법: 위상 정렬(Topological Sort)과 BFS

이 문제는 과목을 노드로, 선수 관계를 방향 간선으로 보는 방향 그래프 문제로 치환할 수 있습니다. 매 학기마다 '현재 이수 가능한 과목', 즉 진입 차수(in-degree)가 0인 노드들을 한꺼번에 수강하는 것이 항상 최적의 전략입니다. 이를 너비 우선 탐색(BFS) 기반의 위상 정렬로 구현하면 다음과 같은 절차로 풀 수 있습니다.

  • courses := n 으로 초기화하고, 크기 n+1의 visited 배열(false), 진입 차수 배열 in_degree(0), 인접 리스트 graph를 준비합니다.
  • relations를 순회하면서 graph[선행 과목]에 후행 과목을 추가하고, 후행 과목의 진입 차수를 1 증가시킵니다.
  • 진입 차수가 0인 모든 과목(선수과목이 없는 과목)을 큐에 넣습니다. 이 과목들이 첫 학기에 수강 가능한 과목들입니다.
  • 큐가 빌 때까지 학기를 반복하며, 각 학기마다 큐에 있는 과목을 모두 이수 처리(completed 개수 증가)하고, 해당 과목을 선수과목으로 갖던 과목들의 진입 차수를 1씩 감소시킵니다.
  • 감소 후 진입 차수가 0이 된 과목은 다음 학기에 수강 가능하므로 새 큐에 삽입합니다. 한 번의 반복이 끝나면 학기 수를 1 증가시킵니다.
  • 모든 과목을 이수했다면(completed == n) 학기 수를 반환하고, 그렇지 않다면 그래프에 순환이 존재한다는 의미이므로 -1을 반환합니다.

구현 예제

class Solution(object):
    def minimumSemesters(self, n, relations):
        # 그래프(인접 리스트)와 진입 차수 초기화
        graph = [[] for _ in range(n+1)]
        in_degree = [0] * (n+1)

        # 선수 관계 등록: prev를 이수해야 nxt를 들을 수 있음
        for prev, nxt in relations:
            graph[prev].append(nxt)
            in_degree[nxt] += 1

        # 진입 차수가 0인 과목 = 첫 학기에 바로 수강 가능한 과목
        queue = [i for i in range(1, n+1) if in_degree[i] == 0]

        semester = 0
        completed = 0

        # 학기 단위로 BFS 수행
        while queue:
            next_queue = []
            for course in queue:
                completed += 1
                for nxt in graph[course]:
                    in_degree[nxt] -= 1
                    if in_degree[nxt] == 0:
                        next_queue.append(nxt)
            queue = next_queue
            semester += 1

        return semester if completed == n else -1


ob = Solution()
print(ob.minimumSemesters(3, [[1, 3], [2, 3]]))

입력 및 실행 결과

입력:

3, [[1,3],[2,3]]

출력:

2

과목 1과 2는 선수과목이 없으므로 첫 학기에 함께 수강할 수 있고, 두 과목을 이수한 뒤에야 선수 조건이 충족되는 과목 3은 두 번째 학기에 수강하게 됩니다. 따라서 최소 학기 수는 2가 됩니다.

복잡도 분석

  • 시간 복잡도: O(N + E) — 모든 과목(N)과 선수 관계 간선(E)을 각각 한 번씩만 처리합니다.
  • 공간 복잡도: O(N + E) — 인접 리스트, 진입 차수 배열, 큐 저장에 필요한 공간입니다.

마무리

이 문제의 핵심은 선수 관계를 그래프로 모델링하고, 매 학기 '동시에 수강 가능한 과목 집합'을 BFS 레벨 단위로 처리하는 것입니다. 만약 일부 과목이 끝내 이수되지 못한다면 그래프 안에 순환(cycle)이 존재한다는 뜻이므로 -1을 반환하면 됩니다. 위상 정렬은 스케줄링, 빌드 순서 결정, 교육 과정 설계 등 다양한 실무 문제에 응용되는 필수 알고리즘이니 꼭 익혀 두시길 바랍니다.