[Leetcode(릿코드)/207] Course Schedule (Medium, Java)

Question

• 문제 링크 : https://leetcode.com/problems/course-schedule/
• 분류 : 위상정렬
• 풀이 시간 : 40분

문제 해설

1. 내가 들어야하는 총 과목의 수 : numCourses
2. 배열 prerequisites
   1. prerequisites[i] = [ai, bi] => ai과정을 수강하려면 먼저 bi 과정을 수강해야 함
3. 모든 과목을 들을 수 있는지 여부 확인

Solution

풀이 접근 방법

1. 선행 과목해야하는 과목 확인 => 위상정렬 이용
2. 위상정렬로 탐색한 과목이 전체 과목 수와 맞으면 모든 과목 수강 가능하다는 의미

정답 코드

class Solution {
    public LinkedList<Integer>[] course;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 과목 수강 그래프
        course = new LinkedList[numCourses];
        
        int[] indegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            course[i] = new LinkedList<Integer>();
        }
        
        for (int[] pre : prerequisites) {
            int start = pre[0];
            int end = pre[1];
            
            course[start].add(end);
            indegree[end]++;
        }
        
        return checkCourse(indegree, numCourses);
        
    }
    
    public boolean checkCourse(int[] indegree, int numCourses) {
        // 탐색 완료한 과목들 넣어줌
        HashSet<Integer> subjects = new HashSet<Integer>();
        // 선행학습 완료된 과목 탐색하기 위한 큐
        Queue<Integer> queue = new LinkedList<Integer>();
        
        // 선행이 필요 없는 과목부터 큐에 넣어줌
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) 
                queue.add(i);
        }
        
        while(!queue.isEmpty()) {
            int subject = queue.poll();
            
            for (int next : course[subject]) {
                indegree[next]--;
                
                if (indegree[next] == 0)
                    queue.add(next);
            }
            
            subjects.add(subject);
        }
        
        if (subjects.size() == numCourses)
            return true;
        return false;
    }
}