[Python] 위상정렬 - 14567. 선수과목 (골5)

14567번: 선수과목 (Prerequisite)

3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다.

www.acmicpc.net

>>문제 포인트

: 위상정렬 문제인데 위상정렬로 안품

: A<B라는 조건을 활용

: 연결정보가 주어지면 무조건 한번 더 들어야 함

: 앞에서부터 최소 학기를 완성하고 하나씩 result 배열 완성해주기

v,e = map(int, input().split())

result = [1]*(v+1)

edge=[]

for _ in range(e):

a,b = map(int, input().split())

edge.append((a,b))

#각 과목 번호로 오름차순 하여 선수과목에 따른 최소이수 학기를 하나씩 완성해감

edge.sort(key=lambda x: (x[1], x[0]))

for i in edge:

result[i[1]]= max(result[i[1]], result[i[0]]+1)

print(*result[1:])

헤이, 브로