[알고리즘, Python] Leetcode - Course Schedule II

과목을 수강할 때 선수과목을 먼저 수강하면서 차례대로 들어야하는 문제이다.

 

문제의 자세한 내용은 아래에서 확인할 수 있다.

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

Course Schedule II - LeetCode

---

문제를 읽고 내가 생각한 것은 1. directed graph 라는것 2. bfs로 구현하면 되지 않을까였다.

 

그렇다면 가장 먼저 들을 과목이 root 노드가 되어야하는데 그런 루트 노드는 어떻게 찾을 수 있을까?

 

노드 중에 선수과목 (prevCourses라고 하자) 이 없는 경우 가장 먼저 들어야하는 과목임을 알 수 있다.

 

하지만 문제에서 connected graph 라는 말이 없으므로 루트노드는 여러개가 될 수 있다.

 

이 세가지 정보를 가지고 다양한 경우의 수를 그려보며 다른 케이스는 없는지 확인해봤다.

 

 

우선 문제에서 순서를 찾을 수 없는 경우 empty array를 리턴하라고 적혀있었는데 만약 두 과목이 서로 선수과목이라고 주장하는 경우(undirected - 양방향인 경우)에는 []를 리턴한다.

 

 

그 다음으로 발견한 점은 아래의 경우 3번이 1과 2 전에 있지만 1은 반드시 2 전에 있어야한다는 것이다.

그림 1

이런 케이스를 어떻게 해결할 수 있을까 고민하다가 Cracking the Coding Interview 문제 4.7의 힌트를 참고했다.

 

힌트에서는 이미 방문한 노드의 엣지를 지우고 다시 prevCourses가 없는 노드를 탐색하는 방법이 있다고 적혀있었다.

 

즉 위의 경우 3을 방문하고 엣지를 지우면 그래프가 아래와 같이 된다.

그림 2

3은 이미 방문했고 방문하지 않은 노드 중에서 1이 prevCourses가 없으므로 1을 방문하면 된다.

 

 

그 다음으로는 아래 그림 처럼 cycle graph인 경우에도 []를 리턴해야 한다.

그림 3

 

코드 구현이 복잡해졌는데 내가 구현한 코드는 아래와 같다.

class Node:
    def __init__(self, num):
        self.num = num
        self.prevs = []
        self.nexts = []

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        courses = [None] * numCourses
        
        for prerequisite in prerequisites:
            nextC, prevC = prerequisite
            try:
                courses[prevC], courses[nextC] = self.makeEdge(courses, prevC, nextC)
            except:
                return []
            
        self.fillNullNodes(courses)
        
        visited = [False] * numCourses
        result = []
        
        while not self.allVisited(visited):
            firstNodes = self.findFirstNodesAndDelete(courses)
            
            if not firstNodes:
                return []
            
            for n in firstNodes:
                visited[n.num] = True
                result.append(n.num)
                
        return result
    
    def makeEdge(self, courses, prevC, nextC):
        if not courses[prevC]:
            prevN = Node(prevC)
        else:
            prevN = courses[prevC]
            
        if not courses[nextC]:
            nextN = Node(nextC)
        else:
            nextN = courses[nextC]
        
        if nextN in prevN.prevs or prevN in nextN.nexts:
            return None

        nextN.prevs.append(prevN)
        prevN.nexts.append(nextN)
        
        return prevN, nextN
    
    
    def fillNullNodes(self, courses):
        nullNodesIdx = [idx for idx, c in enumerate(courses) if not c]
        
        for idx in nullNodesIdx:
            courses[idx] = Node(idx)
    
    
    def findFirstNodesAndDelete(self, courses):
        firstNodes = [c for c in courses if not c.prevs]
        
        for firstNode in firstNodes:
            for nextNode in firstNode.nexts:
                nextNode.prevs.remove(firstNode)
            firstNode.prevs = [2002]
            firstNode.nexts = []
            
        return firstNodes
    
    
    def allVisited(self, visited):
        return not False in visited

코드를 차례대로 설명하자면 우선 모든 course를 가지는 array 인 courses가 있다.

 

그리고 prerequisites를 iterate 하며 엣지를 생성한다.

 

이 경우 양방향을 확인하면(위 코드에서는 makeEdge 가 None을 리턴하는 경우 try catch를 사용했다) 코드를 중단시키고 바로 []를 리턴한다.

 

모든 prerequisites를 확인하고나면 prerequisites에는 포함되어 있지 않은 course가 있을 수 있다.

 

이를 찾기 위해 fillNullNodes를 사용해서 노드를 생성해줬다.

 

왜냐하면 뒤에 findFirstNodesAndDelete 를 실행할 때 None이라면 prevCourses를 불러올 때 NoneType에는 prevCourses가 없다며 에러가 발생할 것이기 때문이다.

 

그런 다음 노드 방문을 체크할 visited 와 결과를 담을 result를 정의한다.

 

그리고 모든 노드를 방문하기전까지 firstNodes 즉 들어오는 엣지가 없는 노드를 모두 찾고, 엣지를 모두 삭제해준다.

 

만약 그림 3처럼 cycle graph인 경우 여기에서 무한 루프를 돌 수 있다.

 

따라서 모든 노드를 방문하지 않았는데 firstNodes가 없는 경우에는 이런 케이스라고 가정할 수 있다. 따라서 []를 리턴한다.

 

제대로 firstNodes를 받은 경우에는 visited 와 reuslt를 알맞게 업데이트 해준다.

 

모든 노드 방문이 끝나면 result를 리턴한다.

---

이 문제는 다양한 케이스를 생각해야하는 문제였다.

 

또한 여전히 코드에서 변수나 함수 이름을 개선하거나 findOrder에 있는 일부 코드를 함수로 만드는 등 개선할 여지가 보인다.

 

그리고 Cracking the Coding Interview 책을 참고하니 DFS를 사용해서 해결하는 방법도 있다고 한다.

 

문제를 처음 해결할 때 레벨순으로 방문해야하니까 BFS를 사용해야한다고 생각하고 BFS를 이용해서 구현했는데 잘 되지 않았다.

 

그 이유는 앞에서 말한 그림 1의 경우를 해결할 수 없었기 때문이다.

 

생각해볼 점이 많아 재밌는 문제였다.

---

Reference

- LeetCode

- Cracking the Coding Interview [Book] by Gayle Laakmann Mcdowell