[Kotlin] 릿코드 207. Course Schedule

📘 문제

leetcode 207. Course Schedule

💡 풀이

• 문제에서 원하는 것은 결국 코스를 순서대로 들을 수 있는지를 물어보는 것이다.
• 여기서 위상 정렬 알고리즘을 사용하면 되겠다고 생각이 들었다.
• Input: numCourses = 2, prerequisites = [[1,0],[0,1]] => false
  이러한 예시를 보면 1번 코스를 들으려면 0번 코스를 완료해야하는데, 다음 인덱스에 있는 값을 보면 0번 코스를 들으려면 1번 코스를 완료해야 한다고 한다.
  그러므로 false라고 한다.
• 이 예시에서 보여주는 것은 시작점이 없다면, 즉 사이클이 있다면 false를 반환하면 된다는 것이다.

💻 코드

fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
    val inDegree = IntArray(numCourses)
    val arr = Array<ArrayList<Int>>(numCourses) { ArrayList() }
    prerequisites.forEach {
        val (a, b) = it
        inDegree[b]++
        arr[a].add(b)
    }
    val queue: Queue<Int> = LinkedList()
    
    for (i in 0 until numCourses) {
        if (inDegree[i] == 0) queue.add(i)
    }
    for (i in 0 until numCourses) {
        if (queue.isEmpty()) return false
        val a = queue.poll()
        for (j in 0 until arr[a].size) {
            val b = arr[a][j]
            inDegree[b]--
            if (inDegree[b] == 0) queue.add(b)
        }
    }
    return true
}

결과