[leetcode] 207. Course Schedule

이 문제는 전형적인 topological sort (위상정렬) 문제입니다.

leetcode.com/problems/course-schedule/

Course Schedule - LeetCode

위키에 topological sort에 대해서 잘 설명되어 있습니다.

ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

위상정렬 - 위키백과, 우리 모두의 백과사전

저는 아래와 같이 접근해봤습니다. (주석 참고)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses+1]; // 해당과목을 선수과목수으로 사용하는 과목의 갯수
        Map<Integer, List<Integer>> map = new HashMap<>(); // 특정 과목의 선수과목 리스트
        
        //map, indegree 초기화
        for(int i=0; i<numCourses; i++) map.put(i, new ArrayList<>());
        for(int i=0; i<prerequisites.length; i++) {
            map.get(prerequisites[i][0]).add(prerequisites[i][1]);
            indegree[prerequisites[i][1]]++;
        }
        
        //queue에 탐색할 과목을 저장함
        //탐색은 indegree가 0인 과목들을 하게 됨
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0; i<numCourses; i++) {
            if(indegree[i] == 0) queue.offer(i);
        }
        
        int checkedCourses = 0;
        while(!queue.isEmpty()) {
            int curr = queue.poll();
            //queue에 존재하는 과목들은 모두 indegree가 0인 과목임
            for(int pre : map.get(curr)) { //해당 과목의 선수과목들을 다시 찾아주고
                indegree[pre]--; //해당 과목을 방문한 것이라는 의미가 되므로 선수과목리스트에서 하나 빼준다.
                if(indegree[pre]==0) queue.offer(pre); //만약에 해당 과목을 선수과목으로 사용하는 과목이 없으면 다시 queue에 넣어준다.
            }
            checkedCourses++; //이렇게 반복문 한번 할 때마다 과목을 한개씩 체크하게 됨
        }
        
        if(checkedCourses == numCourses) return true;
        return false;
    }
}