[LeetCode]Course Schedule

https://leetcode.com/problems/course-schedule/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

강의 과목과 먼저 들어야만 하는 강의 정보가 주어지면, 강의를 모두 수강할 수 있는지 구하는 문제입니다.

 

처음 시도한 답안 

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indegrees = [0] * numCourses

        for post, pre in prerequisites:
            graph[pre].append(post)
            indegrees[post] += 1

        queue = []
        solved = []

        for idx, indegree in enumerate(indegrees):
            if indegree == 0:
                queue.append(idx)

        while queue:
            course = queue.pop(0)
            solved.append(course)
            
            for post in graph[course]:
                indegrees[post] -= 1
                if indegrees[post] == 0:
                    queue.append(post)

        if len(solved) != numCourses:
            return False

        return True

접근 방법

1. 강의 수만큼 이차원 Graph를 생성합니다. 그래프는 각 강의들간의 선수 정보를 담는데 사용됩니다.
2. 강의 수만큼 indegrees를 생성합니다. 각 강의별로 진입 차수(먼저 수강해야하는 강의 수)를 표시하는데 사용합니다.
3. 그래프와 진입 차수 정보를 기록합니다.
4. 진입 차수가 0인 강의들은 수강이 가능하므로 큐에 넣습니다.
5. 큐가 있는동안 반복합니다.
   1. 강의를 큐에서 꺼내고 풀이 처리 합니다.
   2. 해당 강의와 연결된 강의들의 진입 차수를 1 감소합니다.
   3. 만약 감소후 진입 차수가 0이 되었다면 풀이가 가능하므로 큐에 넣습니다.
6. 반복후에 풀이한 문제가 강의수와 다르다면 모두 수강할 수 없는 경우(사이클 발생)이므로 False를 리턴합니다.
7. 아닌 경우 True를 리턴합니다.

선수 강의 문제의 경우에는 위상 정렬 알고리즘을 사용하고 큐로 구현할 수 있습니다.

강의들의 연결 정보를 이차원 그래프로 표현하고 진입 차수를 기록하여 풀이가 가능합니다.

 

만약, prerequisites = [[1,3],[5,2]] 이면 1번 문제는 3번 문제 후에 5번 문제는 2번 문제후에 풀이가 가능한 것입니다. 

따라서 graph = [[][][1][][2]] 로 나타낼 수 있습니다. 즉 graph[2] 3번 문제 다음에 1번 문제 풀이, graph[4] 5번 문제 다음에 2번 문제 풀이가 가능하다는 뜻입니다.