207. Course Schedule (Medium), 210. Course Schedule II

위상정렬이 med로 나오다니 무서운 곳이다

옛날에 열심히 연습했던 것 같은데 오랜만에 보고 1트로 풀어서 뿌듯

deg 가 0인 것부터 진입할 수 있다

from collections import deque
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 위상정렬
        r = {i: 0 for i in range(numCourses)}
        link = {i:[] for i in range(numCourses)}
        fin =[]
        q = deque()
        for pre, cur in prerequisites:
            r[cur]+=1
            link[pre].append(cur)

        for k, val in r.items():
            if val ==0:
                q.append(k)
        while q:
            a = q.popleft()
            fin.append(a)
            for i in link[a]:
                r[i]-=1
                if r[i]==0:
                    q.append(i)
        
        if len(fin)==numCourses:
            return True
        else:
            return False

 

210. Course Schedule II

from collections import deque
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        res=[]
        deg={i: 0 for i in range(numCourses)}
        link = {i:[] for i in range(numCourses)}
        q=deque()

        for cur, pre in prerequisites:
            deg[cur]+=1
            link[pre].append(cur)

        for i, val in deg.items():
            if val ==0:
                q.append(i)
        
        while q:
            a = q.popleft()
            res.append(a)

            for next in link[a]:
                deg[next]-=1
                if deg[next]==0:
                    q.append(next)
        if numCourses ==len(res):
            return res
        else: return []