[leetcode #210] Course Schedule II

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] = [aᵢ, bᵢ] indicates that you must take course bᵢ first if you want to take course aᵢ.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

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

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

Constraints:

・ 1 <= numCourses <= 2000
・ 0 <= prerequisites.length <= numCourses * (numCourses - 1)
・ prerequisites[i].length == 2
・ 0 <= aᵢ, bᵢ < numCourses
・ aᵢ != bᵢ
・ All the pairs [aᵢ, bᵢ] are distinct.

Idea

numCourses가 2000개밖에 되지 않기 때문에 O(n²)으로 풀어도 통과하는 문제다.

뭔가 Graph를 이용할 것 같지만 생각하기가 어려워 우선 Brute force로 풀어보기로 했다.

처음에 주어진 numCourses 만큼 remainingPrerequisites라는 set의 list를 만든다. 해당 자료구조는 각 course 마다 남은 prerequisites를 저장한다.

다음으로 주어진 prerequisites를 돌면서 remainingPrerequisites에 필요한 course들을 저장한다.

수강 가능한 course는 선수 과목이 없어야 하므로 remainingPrerequisites를 돌면서 선수 과목이 없는 과목들만 possibleCourses라는 리스트에 저장한다.

이제 possibleCourses가 비었을 때까지 루프를 돌면서 수강 순서를 정할 수 있다. possibleCourses에서 과목을 하나씩 빼낸 다음 remainingPrerequisites에서 해당 과목을 제거해 나간다. 이 때 제거한 과목을 수강 순서 array에 더한다. 제거 후 prerequisite set이 비어있다면 해당 과목을 possibleCourses에 더한다.

수강 순서의 index가 numCourses랑 일치하지 않을 경우 모든 과목을 듣는 것이 불가능하므로 빈 array를 리턴한다. numCourses랑 일치하는 경우 만들어진 array를 리턴하면 된다.

사실 이렇게 푸는 것은 O(n²)이므로 다른 방법을 연구하는 것이 좋다. leetcode에 Graph와 DFS를 이용한 풀이가 있으므로 참고해서 다시 풀기를!

Solution

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Set<Integer>> remainingPrerequisites = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {
            remainingPrerequisites.add(new HashSet<>());
        }

        for (int[] prerequisite : prerequisites) {
            remainingPrerequisites.get(prerequisite[0]).add(prerequisite[1]);
        }

        List<Integer> possibleCourses = new ArrayList<>();
        for (int i=0; i < numCourses; i++) {
            if (remainingPrerequisites.get(i).isEmpty()) {
                possibleCourses.add(i);
            }
        }

        int[] res = new int[numCourses];
        int index = 0;
        while (!possibleCourses.isEmpty()) {
            int course = possibleCourses.remove(0);
            res[index++] = course;

            for (int i=0; i < numCourses; i++) {
                Set<Integer> set = remainingPrerequisites.get(i);
                if (set.remove(course) && set.isEmpty()) {
                    possibleCourses.add(i);
                }
            }
        }

        if (index != numCourses) {
            return new int[0];
        }

        return res;
    }
}

Graph와 DFS를 이용한 풀이는 다음과 같다.

class Solution {
  static int WHITE = 1;
  static int GRAY = 2;
  static int BLACK = 3;

  boolean isPossible;
  Map<Integer, Integer> color;
  Map<Integer, List<Integer>> adjList;
  List<Integer> topologicalOrder;

  private void init(int numCourses) {
    this.isPossible = true;
    this.color = new HashMap<Integer, Integer>();
    this.adjList = new HashMap<Integer, List<Integer>>();
    this.topologicalOrder = new ArrayList<Integer>();

    // By default all vertces are WHITE
    for (int i = 0; i < numCourses; i++) {
      this.color.put(i, WHITE);
    }
  }

  private void dfs(int node) {

    // Don't recurse further if we found a cycle already
    if (!this.isPossible) {
      return;
    }

    // Start the recursion
    this.color.put(node, GRAY);

    // Traverse on neighboring vertices
    for (Integer neighbor : this.adjList.getOrDefault(node, new ArrayList<Integer>())) {
      if (this.color.get(neighbor) == WHITE) {
        this.dfs(neighbor);
      } else if (this.color.get(neighbor) == GRAY) {
        // An edge to a GRAY vertex represents a cycle
        this.isPossible = false;
      }
    }

    // Recursion ends. We mark it as black
    this.color.put(node, BLACK);
    this.topologicalOrder.add(node);
  }

  public int[] findOrder(int numCourses, int[][] prerequisites) {

    this.init(numCourses);

    // Create the adjacency list representation of the graph
    for (int i = 0; i < prerequisites.length; i++) {
      int dest = prerequisites[i][0];
      int src = prerequisites[i][1];
      List<Integer> lst = adjList.getOrDefault(src, new ArrayList<Integer>());
      lst.add(dest);
      adjList.put(src, lst);
    }

    // If the node is unprocessed, then call dfs on it.
    for (int i = 0; i < numCourses; i++) {
      if (this.color.get(i) == WHITE) {
        this.dfs(i);
      }
    }

    int[] order;
    if (this.isPossible) {
      order = new int[numCourses];
      for (int i = 0; i < numCourses; i++) {
        order[i] = this.topologicalOrder.get(numCourses - i - 1);
      }
    } else {
      order = new int[0];
    }

    return order;
  }
}

Reference

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