Course Schedule

LeetCode - The World's Leading Online Programming Learning Platform

문제 파악 [필수 작성]

문제이해

전형적인 위상정렬 문제
prerequisites[i] = [ai, bi] 이 주어지는데
ai 가 더 어려운 과목
bi 가 더 쉬운 과목
b를 수강해야 a를 수강할 수 있음
전체 리스트가 주어졌을때 끝까지 수강할수 있는지 여부를 체크하는 문제

제한 조건 확인

numCourses 최대 2000
prerequisites.length 는 최대 5000
-> 선후관계가 정의된게 최대 5000개
각각의 선후관계 길이는 최대 2, 즉 앞뒤관계만 있음, 여러관계는 없음

아이디어

전형적인 위상정렬 indegree 접근방법을 활용하면 가능할것 같다.
prerequisites 을 다 돌아서 indegree 값을 각 노드에 대해 구해준 후
indegree 값이 0 인 것들을 큐에 삽입 후
큐에 원소가 없을때까지
현재 큐에서 한개 뽑아서
다음 노드로 연결되는 노드의 indegree 를 한개 지워주고
만약 -1 한 노드의 indegree 가 0 이면
큐에 해당 노드를 추가

최종적으로 모든 노드를 순회탐색했을때 아직도 indegree 가 0이 아닌게
하나라도 있으면 return False
다 0 이면 return True

시간복잡도

계산할 필요도 없이 충분할 것으로 보임

자료구조

각 노드의 연결관계를 나타내주는 Linked_list = {} {출발노드:[도착노드들]}
각 노드의 indegree 값을 나타내는 list = []
특정 노드를 방문했는지 확인하는 list

접근 방법 [필수 작성]

아이디어

코드 구현 [필수 작성]

from collections import defaultdict
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        visited = [False for _ in range(numCourses)]
        indegree = [0 for _ in range(numCourses)]
        links = defaultdict(list) #value 가 있는 key는 리스트형태로 반환, value가 없는 key는 빈 리스트
        for hard,easy in prerequisites:
            links[easy].append(hard)
            indegree[hard] += 1

        q = deque([])
        for node_num in range(len(indegree)):
            if indegree[node_num] == 0:
                q.append(node_num)
                visited[node_num] = True
    
        while q:
            tmp_node = q.popleft()
            for next_node in links[tmp_node]:
                indegree[next_node] -= 1
                if indegree[next_node] == 0:
                    q.append(next_node)
                    visited[next_node] = True

        for v in visited:
            if v == False:
                return False
        return True

배우게 된 점 [필수 작성]

선후관계 설정해줄때 dict 와 indegree 리스트에 해당되는 값을 처음에는 거꾸로 설정해줘서 문제가 됐었다.

dict 의 각 key값은 목적노드의 인덱스를 value 로 가지지만, indegree의 각 인덱스의 값들은 본인에게 몇개의 edge 가 들어오는지를 기록해줘야한다.

즉, dict 의 각 key 값의 value 의 갯수가 indegree 의 key인덱스의 값이 아니다!!

질문 [ 필수 X ]

댓글로 또는 이곳에 질문 남겨주세요.