Daily LeetCode Challenge - 207. Course Schedule

Problem From.

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

오늘 문제는 prerequisites 배열이 주어졌을때, 규칙에 따라 모든 수업을 들을 수 있으면 true 아니면 false 를 반환하는 문제였다. 규칙은 배열의 원소들 중에서 첫번째 원소를 들으려면 두번째 원소를 먼저 들어야한다는 규칙이었다.

이 문제는 dfs 를 통해서 풀 수 있었는데, 먼저 prerequiets 배열을 탐색하며 map 형식으로 각각의 수업을 듣기 위한 prerequisites 를 짝지어서 정리해둔다. 그런 다음 dfs 를 통해서 map 을 탐색하면서 모든 수업을 들을 수 있는지 검사해주면 되었다.

 class Solution {
    fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
        if (numCourses < 2) return true
        
        val preMap = mutableMapOf<Int, MutableList<Int>>()
        for (pre in prerequisites) {
            val (course, mandatory) = pre
            preMap.getOrPut(course) { mutableListOf() }.add(mandatory)
        }
        
        val visit = IntArray(numCourses + 1)
        for (courseNum in 0 until numCourses) {
            if (!dfs(courseNum, visit, preMap)) {
                return false
            }
        }
        return true
    }
    
    fun dfs(courseNum: Int, visit: IntArray, preMap: Map<Int, List<Int>>): Boolean {
        if (visit[courseNum] == 1) {
            return false 
        } else if (visit[courseNum] == 2) {
            return true
        }
        
        visit[courseNum] = 1
        
        val prerequisites = preMap[courseNum]
        if (prerequisites != null) {
            for (pre in prerequisites) {
                if (!dfs(pre, visit, preMap)) {
                    return false
                }
            }
        }
        
        visit[courseNum] = 2
        
        return true
    }
}