DFS/BFS_Leetcode_Course Schedule

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

Course Schedule - LeetCode

접근 방법

1. prerequisites를 검사하여, 선이수 과목이 필요없는 과목을 찾는다.

2. 이를 스택에 넣고, 하나씩 제거하며, 후수과목을 찾아 스택에 넣는다.

3. 이를 반복하여, 이수가능 과목과 numCourses를 비교하여 반환한다.

틀린 코드

사유 : 선수과목이 [1,4],[2,4] 와 같이 있을경우, 둘 중 하나 [1,4] 만 확인됨. -> first()에 의해서.

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var completion : Set<Int> = []
        var requisities : Set<Int> = []
        var stack : [Int] = []
        
        for pre in prerequisites {
            requisities.insert(pre[0])
        }
        
        for i in 0..<numCourses {
            if !requisities.contains(i) {
                completion.insert(i)
                stack.append(i)
            }
        }
        
        while !stack.isEmpty {
            let target = stack.removeLast()
            guard let pre = prerequisites.first(where: { $0[1] == target}) else {continue}

            completion.insert(pre[0])
            stack.append(pre[0])
        }
        
        print(numCourses == completion.count, completion.count, numCourses)
        
        return numCourses == completion.count
    }
}

위의 코드를 아래와 같이 수정하여 오류 수정.

하지만 testcase :

3
[[1,0],[1,2],[0,1]]

가 실패함.

 

선수 교과목이 없는 2는 수강 가능하므로,

2를 수강하면, 1을 수강 할 수 있고,

1을 수강 할 수 있으므로 0을 수강 할 수 있는게 아닌가?

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var completion : Set<Int> = []
        var requisities : Set<Int> = []
        var stack : [Int] = []
        var preRequisites = prerequisites
        
        for pre in preRequisites {
            requisities.insert(pre[0])
        }
        
        for i in 0..<numCourses {
            if !requisities.contains(i) {
                completion.insert(i)
                stack.append(i)
            }
        }
        
        while !stack.isEmpty {
            print(stack)
            let target = stack.removeLast()
            
            let indexArray = preRequisites.filter({
                $0[1] == target
            })
            
            for index in indexArray {
                completion.insert(index[0])
                stack.append(index[0])
                preRequisites.remove(at: preRequisites.firstIndex(of: index)!)
            }
            
            
        }
        
        print(numCourses == completion.count, completion.count, numCourses, preRequisites)
        
        return numCourses == completion.count
    }
}