📕문제

[Leetcode] 207. Course Schedule

문제 설명

과목의 개수인 numCourses와 각 과목을 수강하기 위한 선수과목을 나타내는 리트스인 prerequisites가 주어졌을 때 모든 과목을 수강할 수 있는지 구하는 문제다.

예를 들어 numCourses = 2, prerequisites = [[0, 1]] 인 경우
1은 선수과목이 존재하지 않고 0은 1을 수강해야만 수강할 수 있으므로 모든 과목을 수강할 수 있다.

---

📝풀이

처음에 문제를 잘못 이해했다..
선수과목 중 하나라도 들었다면 해당 과목을 수강할 수 있다고 생각해 다음과 같이 풀었다.

from collections import defaultdict
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        courses = defaultdict(list)
        available = list(range(numCourses))

        for req in prerequisites:
            courses[req[1]].append(req[0])
            if req[0] in available:
                available.remove(req[0])
        

        for i in available:
            for course in courses[i]:
                if course not in available:
                    available.append(course)
        
        return len(available) == numCourses

• 딕셔너리에 해당 과목을 수강하면 수강할 수 있는 과목들을 저장한다.
• 선수과목이 존재하지 않는 과목을 available에 남겨두고 딕셔너리 값을 이용해 해당 리스트에 값을 추가해가며 수강할 수 있는 과목을 업데이트했다.

문제를 제대로 읽어보니 과목을 수강하려면 모든 선수과목을 수강해야 한다는 것을 알았다.
또한 제시된 조건 중 prerequisites에 존재하는 모든 페어에 중복이 존재하지 않다는 것도 알게되었다.
즉 선수과목이 어떤 과목인지 알 필요 없이 개수만 세면 된다.

from collections import defaultdict, deque
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        courses = defaultdict(list)
        preNum = [0] * numCourses

        for pair in prerequisites:
            courses[pair[1]].append(pair[0])
            preNum[pair[0]] += 1
        
        count = 0
        queue = deque()
        
        for i in range(numCourses):
            if preNum[i] == 0:
                queue.append(i)
        
        while queue:
            current = queue.popleft()
            count += 1

            for course in courses[current]:
                preNum[course] -= 1
                if preNum[course] == 0:
                    queue.append(course)

        return count == numCourses

• 딕셔너리에 해당 과목을 수강하면 수강할 수 있는 과목을 저장한다. 동시에 선수과목의 개수도 업데이트 한다.
• 선수과목이 존재하지 않는 과목을 큐에 삽입한다.
• 큐에서 과목을 꺼내며 해당 과목을 선수과목으로 가지는 과목의 선수과목 개수를 1 줄인다.
• 선수과목의 개수가 0이 되면 수강할 수 있다는 뜻이므로 큐에 추가한다.
• 수강할 수 있는 과목의 수와 전체 과목의 수를 비교해 반환한다.

문제 설명이 영어로 되어있다보니 문제를 정확하게 이해하지 못했다.
또한 중복이 존재하지 않는다는 조건을 알지 못했다면 더 어렵게 풀었을 것 같다.
앞으로 문제를 더 꼼꼼하게 읽어야겠다.