Python으로 모든 과목을 수강하기 위한 최소 학기 수 계산하기

문제 설명

n개의 서로 다른 과목이 있으며, 각 과목에는 1부터 n까지 번호가 붙어 있다고 가정해 보겠습니다. 또한 relations 배열이 주어지는데, relations[i]는 (선수과목_i, 후속과목_i) 쌍을 담고 있어 두 과목 사이의 선수 관계를 나타냅니다. 즉, 후속과목_i를 수강하려면 반드시 먼저 선수과목_i를 이수해야 합니다.

마지막 매개변수인 k는 한 학기에 수강할 수 있는 최대 과목 수를 의미합니다. 단, 어떤 과목을 수강하려면 그 과목의 선수과목들을 이전 학기까지 모두 이수한 상태여야 합니다. 우리의 목표는 모든 과목을 수강하는 데 필요한 최소 학기 수를 구하는 것입니다.

예시

예를 들어 입력이 다음과 같다고 해봅시다.

n = 6
relations = [(1,3), (2,5), (2,4), (5,6)]
k = 2

이 경우 출력은 3입니다. 첫 번째 학기에는 선수과목이 없는 과목 1과 2를 수강할 수 있습니다. 그러면 두 번째 학기에 과목 3, 4, 5를 들을 자격이 생기는데, 한 학기에 최대 2과목까지만 수강할 수 있으므로 과목 5와 과목 3 또는 4 중 하나를 선택합니다. 세 번째 학기에 나머지 과목(과목 6 포함)을 모두 마칠 수 있으므로, 총 3학기가 필요합니다.

풀이 접근 방법

이 문제는 위상 정렬(Topological Sort)과 탐욕(Greedy) 전략을 결합하여 해결할 수 있습니다. 핵심 아이디어는 한 학기에 들을 수 있는 과목이 k개보다 많을 때, 후속 과목이 많은 과목(가중치가 높은 과목)을 우선적으로 선택하는 것입니다. 이렇게 하면 다음 학기에 새롭게 수강 가능해지는 과목 수를 최대화할 수 있습니다.

단계별 풀이 과정은 다음과 같습니다.

taken := 지금까지 수강 완료한 과목을 저장하는 새로운 집합
g1 := n개의 빈 리스트로 구성된 리스트 (각 과목의 선수과목 목록)
g2 := n개의 빈 리스트로 구성된 리스트 (각 과목의 후속과목 목록)
w := 크기가 n이고 0으로 초기화된 리스트 (각 과목의 가중치)
semester := 0 (학기 카운터)
relations의 각 x에 대해 다음을 수행합니다.
- g1[x[1]-1]의 끝에 x[0]-1을 삽입합니다.
- g2[x[0]-1]의 끝에 x[1]-1을 삽입합니다.
weight := g1의 각 항목(선수과목 개수)의 길이로 만든 새로운 리스트
i를 0부터 n-1까지 반복하며, g1[i]의 각 x에 대해 w[x]를 w[x]와 weight[i] 중 더 큰 값으로 갱신합니다.
taken의 크기가 n보다 작은 동안 다음을 반복합니다.
- courses := 새로운 리스트
- i를 0부터 n-1까지 반복하며, g1[i]가 비어 있고 i가 taken에 없다면 courses에 (i, w[i])를 삽입합니다.
- courses의 크기가 k보다 크면, 두 번째 요소(가중치)를 기준으로 내림차순 정렬한 뒤 앞에서 k개만 남깁니다.
- semester를 1 증가시킵니다.
- courses의 각 x에 대해 다음을 수행합니다.
  - g2[x[0]]의 각 y에 대해 g1[y]에서 x[0]을 제거합니다.
  - g2[x[0]]을 빈 리스트로 초기화합니다.
  - x[0]을 taken에 추가합니다.
semester를 반환합니다.

구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

def solve(n, relations, k):
    taken = set()
    g1 = [[] for _ in range(n)]
    g2 = [[] for _ in range(n)]
    w = [0] * n
    semester = 0
    for x in relations:
        g1[x[1]-1].append(x[0]-1)
        g2[x[0]-1].append(x[1]-1)

    weight = list(map(len, g1))
    for i in range(n):
        for x in g1[i]:
            w[x] = max(w[x], weight[i])

    while len(taken) < n:
        courses = []
        for i in range(n):
            if (not g1[i]) and (i not in taken):
                courses.append([i,w[i]])
        if len(courses) > k:
            courses = sorted(courses, key = lambda x:x[1],reverse=True)
            courses = courses[:k]

        semester += 1

        for x in courses:
            for y in g2[x[0]]:
                g1[y].remove(x[0])
            g2[x[0]] = []
            taken.add(x[0])
    return semester

n = 6
relations = [(1,3),(2,5),(2,4),(5,6)]
k = 2
print(solve(n, relations, k))

입력

6, [(1,3),(2,5),(2,4),(5,6)], 2