LeetCode - 207. Course Schedule - swift

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

Course Schedule - LeetCode

 

numCourse 라는 숫자변수가 총 들어야하는 수강과목 수 이다.

prerequisits [Int] 배열이 들어오는데, 각각  [ a, b ] 를 갖는데,

이는 a를 수강하기 위해서는 b를 필수적으로 수강해야 한다는 뜻이다. 

a, b 는 numCourse보다 무조건 작은 숫자이다. 

 

prerequisit을 잘 판별하여, 모든 과목들을 수강할 수 있는지 판별하는 문제다. 

 

이런 문제는 위상정렬의 알고리즘으로, 

위상정렬의 뜻을 알고 있지 않아도 각 노드들의 관계를 잘 파악하고, bfs로 잘 구현한다면 풀 수 있다.

 

위상정렬은 보통 순서가 있는 노드들이면서, 차례대로 진행해야 하는 경우에 쓰인다.

진입차수 라는 용어가 사용되는데, 이는 특정 노드를 방문하기 위해서는, 해당 노드의 진입차수가 0이여야 한다. 

이것을 이 문제와 잘 섞어보면, 진입차수는 이 문제에서 특정 과목을 수강하기 위해서 필수적으로 수강해야하는 과목의 수 라고 할 수 있다.

 

즉 진입차수 관련된 변수를 만들어주고,  - remainToTake [ i ] = i 과목을 수강하기 위해서 필수적으로 수강해야하는 과목의 수 

 

prerequisits변수들을 이용하여 진입차수 변수들을 초기화해준다. 

 

그리고, prerequisits변수를 이용하여, 노드관계도 표현하는 노드변수를 만들어준다.  nodes [ i ] = i 과목을 수강한다면 수강할 수 있는 과목들 

 

모두 초기화했다면, 이제 bfs탐색을 해야하고, 큐는 remainToTake에서 0인값들을 넣어준다. 

이제 탐색하는 과정은, 필수적으로 수강해야하는 과목들이 모두 수강한 경우에만 큐에 넣어주도록 한다.

이미 0인값은 우선적으로 수강해야하는 과목이 없다는 뜻이겠다. 

 

큐에서 꺼낸 노드들을, nodes변수를 이용하여 수강할 수 있는 과목들을 탐색하는데,

remainToTake에서 -1을 한다. 

만약 0이된다면 선수조건을 만족했으므로, 큐에 넣어준다. 

 

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var remainsToTake = Array(repeating: 0, count: numCourses)
        var nodes = Array(repeating: [Int](), count: numCourses)
        var queue = [Int]()
        var course = 0
        var q = 0
        
        prerequisites.forEach {
            nodes[$0[1]].append($0[0])
            remainsToTake[$0[0]] += 1
        }
        
        for i in 0..<numCourses {
            if remainsToTake[i] == 0 {
                queue.append(i)
            }
        }
        
        while queue.count > q {
            let f = queue[q]
            q += 1
            course += 1
            for next in nodes[f] {
                remainsToTake[next] -= 1
                if remainsToTake[next] == 0 {
                    queue.append(next)
                }
            }
        }
        return course == numCourses
    }
}