[LeetCode] 207. Course Schedule

문제

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

Course Schedule - LeetCode

———————————————————————————

 

잠깐만

로직에 대한 아이디어가 없으면 코드를 바로 보세요.

———————————————————————————

 

코드

class Solution {
    let visited = 1     //이전에 방문한 course에 대한 값
    let visiting = -1   //지금 방문 중인 course에 대한 값
    
    var courseCurriculum: [[Int]]?  //각 course에 대한 커리큘럼 저장
    var isVisit: [Int]?             //DFS시 방문 여부 저장
    
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        courseCurriculum = Array(repeating: [Int](), count: numCourses)
        isVisit = Array(repeating: 0, count: numCourses)
        
        for node in prerequisites {
            let courseNum = node[0]     //courseNum
            let preCourseNum = node[1]  //course에 대한 사전 course
        
            courseCurriculum![courseNum].append(preCourseNum)
        }
    
        for index in 0..<numCourses {   //DFS시작
            if !checkCourse(courseNum: index) {
                return false
            }
        }
        return true
    }

    func checkCourse(courseNum: Int) -> Bool {
        if isVisit![courseNum] == visited {    //이전에 visit하여 검증 완료했을 때,
            return true                         //추가 검증하지 않고 종료
        } else if isVisit![courseNum] == visiting {    //지금 방문중일때,
            return false                                //한번 더 방문했다면 cycle 형성을 의미
        }
    
        isVisit![courseNum] = visiting    //지금 방문중임을 표시
    
        for index in courseCurriculum![courseNum] { //다음 course 체크
            if !checkCourse(courseNum: index) {
                return false
            }
        }
        isVisit![courseNum] = visited       //방문이 끝났으니, 값을 방문 했음으로 변경
        return true
    }
}

———————————————————————————

 

설명

문제에서 설명하는 "[[1,0],[0,1]]"는 싸이클을 의미합니다.

우리는 노드를 따라 가면서 싸이클이 존재하는지 확인하면 됩니다.

 

1. 각 course마다 가지고 있는 preCourse(먼저 수강해야 하는 course)를 저장합니다.

2. 각 course에 대한 체크를 합니다. DFS

3. 방문 여부를 체크 합니다.

- 이미 방문하여 문제없음을 체크한 상태면, 더이상 체크하지 않고 true(정상)로 리턴합니다.

- 방문중에, 다시 한번더 방문했다면 싸이클이 발생했다는 의미이며, false(비정상)으로 리턴합니다.

4. 첫 방문이라면, 방문중임을 체크하고, 지금 확인 중인 course에 대한 preCourse를 체크합니다.

5. 방문이 완료되면, "방문 중"을 "방문 완료"로 체크합니다.

 

이를 코드로 구현하였으며, 주석 또한 추가하였습니다.

로그를 찍어봐도 큰 도움이 될거에요.

———————————————————————————

 

회고

그래프 문제를 오랜만에 풀어보니 어렵네요;;;

다른 문제풀이를 통해 개념좀 다시 잡고 와야겠어요!!