숫자 n이 있다고 가정하고 1에서 n까지 레이블이 지정된 n개의 다른 코스가 있음을 나타냅니다. 우리는 또한 관계[i]가 한 쌍(prevCourse_i, nextCourse_i)을 포함하는 관계라는 배열을 가지고 있습니다. 이는 prevCourse_i 과정과 nextCourse_i 과정 사이의 전제 관계를 나타냅니다. 따라서 prevCourse_i 과정은 nextCourse_i 과정보다 먼저 수강해야 합니다. 그리고 우리가 가지고 있는 마지막 매개변수는 k입니다. 한 학기에 수강하는 과목에 대해 이전 학기에 모든 선수 과목을 이수했다면 최대 k 과목을 수강할 수 있습니다. 모든 과정을 수강하는 데 필요한 최소 학기 수를 찾아야 합니다.
따라서 입력이 다음과 같으면
첫 번째 학기에는 과정 1과 2를 들을 수 있기 때문에 출력은 3이 될 것입니다. 이제 우리는 과정 3, 4, 5에 적격하므로 두 번째 학기에 5와 3 또는 4 중 하나를 선택하면 다음 학기에 모든 과정을 마칠 수 있습니다. 따라서 총 3학기가 필요합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
촬영:=새로운 세트
-
g1 :=n개의 빈 목록이 있는 목록
-
g2 :=크기가 n이고 0으로 채워진 새 목록
-
w :=크기가 n이고 0으로 채워지는 새 목록
-
학기 :=0
-
관계의 각 x에 대해 수행
-
g1[x[1]-1]
끝에 x[0]-1 삽입 -
g2[x[0]-1]
끝에 x[1]-1 삽입
-
-
weight :=g1에 있는 모든 항목의 길이에서 새 목록
-
범위 0에서 n - 1에 있는 i에 대해 수행
-
g1[i]의 각 x에 대해 수행
-
w[x] :=w[x]와 weight[i]의 최대값
-
-
-
의 크기가
-
코스 :=새 목록
-
범위 0에서 n - 1에 있는 i에 대해 수행
-
g1[i]가 비어 있고 i가 취해지지 않은 경우
-
코스 끝에 (i, w[i]) 삽입
-
-
코스의 크기> k인 경우
-
코스 =두 번째 매개변수를 기준으로 코스를 역순으로 정렬
-
코스 :=처음 k 코스 목록
-
-
학기 :=학기 + 1
-
과정의 각 x에 대해 수행
-
g2[x[0]]의 각 y에 대해 수행
-
g1[y]에서 x[0] 삭제
-
-
g2[x[0]] :=빈 목록
-
x[0] 삽입
-
-
-
-
반환 학기
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
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
출력
3