[LeetCode] 207. Course Schedule

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

---

Solution

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] dependency = new int[numCourses];
        for (int[] pair : prerequisites)
            dependency[pair[0]]++;
        
        Queue<Integer> queue = new LinkedList<>(); // Queue for courses ready
        for (int i = 0; i < dependency.length; i++)
            if (dependency[i] == 0)
                queue.add(i);
        
        int finished = 0;
        while (!queue.isEmpty()) {
            finished++;
            int course = queue.poll();
            for (int[] pair : prerequisites) {
                if (pair[1] == course) {
                    dependency[pair[0]]--;
                    if (dependency[pair[0]] == 0) {
                        queue.add(pair[0]);
                    }
                }
            }
        }
        return numCourses == finished;
    }
}

Explanation

• 2차원 배열 prerequsites의 속의 한 배열 [0, 1]에서 0은 1에 의존성을 가지고 있다고 할 때, 각 Course의 의존성을 찾아야 수강할 수 있는 Course와 수강할 수 없는 Course를 나눌 수 있다.
• 의존성을 조사하기 위해 배열 dependency를 선언한다. 배열의 길이는 numCourses값으로 하여 가능한 모든 Course의 의존성을 알아보도록 한다. 그리고 의존성이 있는 Course를 인덱스로 하여 의존성이 있으면 해당 요소의 값을 증가시킨다.

  int[] dependency = new int[numCourses];
  for (int[] pair : prerequisites)
    dependency[pair[0]]++;
  

• 의존성이 없는 Course를 파악하고, 해당 Course를 수강한 후 의존성이 사라지는 Course를 찾기 위해서 자료구조를 선언해야 한다. 의존성 조사를 위해 2차원 배열 prerequsites를 들여다 볼 때 Course들은 선입선출 형태를 유지해야 하므로 자료구조 Queue를 선언한다. 그리고 의존성이 없는 Course를 Queue에 추가한다.

  Queue<Integer> queue = new LinkedList<>(); // Queue for courses ready
  for (int i = 0; i < dependency.length; i++)
    if (dependency[i] == 0)
        queue.add(i);
  

• 수강을 완료한 Course의 수를 파악하기 위해 변수 finished를 선언하고, 의존성이 없어 수강 준비가 된 Course를 가지고 있던 Queue에서 Course를 제거하면서 변수 finised의 값을 증가시킨다.

  int finished = 0;
  while (!queue.isEmpty()) {
    finished++;
    queue.poll();
  }
  

• 의존성이 없는 Course를 수강하여 의존성이 사라지는 Course를 찾아 의존성을 줄이고, Queue에 추가하기 위하여 for반복문과 if조건문을 사용한다.

  while (!queue.isEmpty()) {
    finished++;
    int course = queue.poll();
    for (int[] pair : prerequisites) {
        if (pair[1] == course) {
            dependency[pair[0]]--;
            if (dependency[pair[0]] == 0) {
                queue.add(pair[0]);
            }
        }
    }
  }
  

• 수강을 완료한 Course와 변수 numCourses를 비교하여 결과를 반환한다.

  return numCourses == finished;