💯 Daily LeetCode Challenge Day_18 - Course Schedule 2

Account Login - LeetCode

---

문제

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:
Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   course 0. So the correct course order is [0,1] .

Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.   So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

---

선 이수 과목이 정해 져 있을때 커리큘럼을 마칠 수 있는 순서를 정하는 문제이다.

그래프 문제인건 알겠다.

unweighted, directed, Acyclic 의 키워드로 찾아보니 Topological sort (위상정렬) 문제 였다.

[알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog

계획은 그래프를 인접리스트로 만들고 dfs 로 탐색하며 위상정렬한 뒤 답을 반환할 것이다.

먼저 그래프에 대한 인접 리스트를 만들어 준다.

var graph : [[Int]] = Array(repeating: [Int]() , count: numCourses)
        for i in prerequisites {
            let from = i[1]
            let to = i[0]
            graph[from].append(to)
        }

그 다음 위상 정렬을 할건데 특이한게 cycle이 있으면 안되므로 visited 의 상태가 3가지가 된다.

1. unvisited : 0 (초기상태)
2. in stack   : 1 (사이클 확인용)
3. visited    : 2 (다시는 안볼것)

 

*cycle detection 참고자료

 

순서를 보관할 stack 과 vertex 상태를 담을 visited 를 선언한다.

   var stack : [Int] = []
   // 0: unvisited 1: in stack 2: visited
   var visited : [Int] = Array(repeating: 0, count: numCourses)

---

모든 unvisited 한 vertex 를 돌며 dfs 방식으로 iterate 한다.

        for i in 0..<numCourses {
            if visited[i] == 0 && dfs(i, graph, &stack, &visited) {
                return []
            }
        }

---

여기서 dfs 의 리턴은 Bool 인데 cycle 이 있을경우 true 를 반환하여 빈 배열을 답으로 제출한다.

dfs 함수는 u라는 vertex 에 대한 인접 vertex 를 돌며 visited 가 1일 경우 (stack 에 있을 경우) cycle 로 판단하고 0 일 경우 backtracking 해준다.

그리고 해당 u 라는 vertex를 2로 만들어 주고 stack 에 추가해 준 다음 false 를 반환한다.

    func dfs(_ u : Int, _ graph : [[Int]], _ stack:inout[Int],_ visited:inout[Int]) -> Bool{
        visited[u] = 1
        for v in graph[u] {
            if visited[v] == 1 {return true} //cycle detected
            if visited[v] == 0 && dfs(v, graph, &stack, &visited) {return true}
        }
        visited[u] = 2
        stack.append(u)
        return false //no cycle
    }

---

전체코드

class Solution {
    func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
        var answer : [Int] = []
        
        var graph : [[Int]] = Array(repeating: [Int]() , count: numCourses)
        for i in prerequisites {
            let from = i[1]
            let to = i[0]
            graph[from].append(to)
        }
        var stack : [Int] = []
        // 0: unvisited 1: visited, but not all visited
        var visited : [Int] = Array(repeating: 0, count: numCourses)
        for i in 0..<numCourses {
            if visited[i] == 0 && dfs(i, graph, &stack, &visited) {
                return []
            }
        }
        return stack.reversed()
    }
    func dfs(_ u : Int, _ graph : [[Int]], _ stack:inout[Int],_ visited:inout[Int]) -> Bool{
        visited[u] = 1
        for v in graph[u] {
            if visited[v] == 1 {return true} //cycle detected
            if visited[v] == 0 && dfs(v, graph, &stack, &visited) {return true}
        }
        visited[u] = 2
        stack.append(u)
        return false //no cycle
        
    }
}

 

[필요했던 지식]

• Topological sorting
• Depth First Search (DFS)
• Detecting Cycle in Directed Graph
• Making Adjacency List of Directed Graph