문제

• numCourses: 들어야하는 과목 수
• prerequisites: 선행 과목 관계 (b를 먼저듣고, a 들어야함)
• 모든 코스 들을 수 있으면 true, 못들으면 false

풀이

• 위상정렬 문제
• 선행 과목의 수로 정렬하는 것 -> 위상정렬
• 선행과목이 0개인 것 부터 돌면 됨
• 선행 과목의 수를 저장하는 status
• A ->B, A ->C라고 했을 때, A가 수행되면 B,C의 state를 -1 해주는 것이 포인트

from collections import defaultdict, deque
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        status = [0 for _ in range(numCourses)]
        preToPost = defaultdict(list) # {pre course: [post courses]}
        for post, pre in prerequisites:
            status[post] += 1
            preToPost[pre].append(post)
        
        q = deque() # waiting Q
        countCourses = 0 # to compare at last
        for num, state in enumerate(status):
            if state == 0:
            	# state가 0인 과목들은 지금 당장 수강 가능
                q.append(num) # push to Q
                countCourses += 1
        while q:
            thisNode = q.popleft()
            for nextNode in preToPost[thisNode]:
                status[nextNode] -= 1 # 이 과목을 수강하면, 수강할 수 있는 후행 과목들의 state - 1 해주기
                if status[nextNode] == 0:
                	# 선행과목 수강 덕에, state 0 되면 얘도 Q에 들어갈 수 있음
                    q.append(nextNode)
                    countCourses += 1
        if countCourses == numCourses:
            return True
        else:
            return False

결과

위상정렬 기억 못할 줄 알았는데 했네..
다소 느리다는 문제가 좀 있네,,,