[LeetCode] Course Schedule 2

Course Schedule II - LeetCode

문제 풀이 (최악의복잡도): naive하게 풀기

n이 2000이기 때문에 전체탐색으로도 풀 수 있다.

매 번 다음에 수강할 노드를 탐색하여 선택할 수 있다.

• 아직 수강하지 않은 강의 중에, 필수수강 강의들을 모두 수강한 첫 번째 강의 를 선택한다.

• 탐색 : O(n^2)
• 탐색을 n 번
  하게 되니
  최악은 O(n^3)이 나와야할 것 같은데

이거로도 풀리긴 했다

class Solution {
  public List<Integer>[] parents = new List[2001];
  public boolean[] visit = new boolean[2001];

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

    // 노드들을 방문한 순서를 담고 있는 answer -> 노드의 개수만큼의 사이즈를 갖는다
    int[] answer = new int[numCourses];

    // init
    for (int i = 0; i < numCourses; i++) parents[i] = new ArrayList<>();
    for (int[] pre: prerequisites){
      parents[pre[0]].add(pre[1]);
    }

    int next = -1; 
    // 노드의 개수 만큼 노드들을 방문한다
    for(int cnt = 0 ; cnt < numCourses; cnt++){
      // cnt 개 만큼의 노드들을 방문하기 전에, 더 이상 다음 방문할 노드가 없다면 empty array 
      if ((next = findNext(numCourses)) == -1) return new int[0];
      visit[next]  = true;
      answer[cnt] = next;
    }
    return answer;

  }

  // 다음에 방문할 노드 찾기
  public int findNext(int numCourses){
    for(int i = 0 ; i< numCourses;i++){
      if(visit[i]) continue;
      if(!satisfy(i)) continue;
      return i; 
    }
    return -1;
  }
  
  // preRequisites 를 만족하는가
  public boolean satisfy(int n){
    for (Integer integer : parents[n]) {
      if (!visit[integer]) return false;
    }
    return true;
  }

}

문제 풀이 : 다른 풀이 : 위상정렬

코스스케줄 1 은 dfs 로 풀었던 기억이 있었으나 코스 스케줄 2를 dfs 로 풀 방법을 찾지 못했었다.

• 위상정렬 알고리즘을 사용한다는 풀이를 보았다.

이제까지 위상정렬 알고리즘을 공부한 적이 없었다..;;
동빈나님의 강의를 찾아서 들었다.

• 위에서 naive하게 풀 때도 그러했듯이, 위상정렬 알고리즘을 사용할 때도 중요한 것은, 결국 numCourses 개수 만큼의 노드에 대해서만 수행해야한다는 것이다.
  • q에는 총 numCourses 개의 노드가 들어갔다가 꺼내져야 한다. 이보다 적은 수의 노드가 들어갔었다면, 사이클이 발생했음을 의미한다. ( cycle이 존재하는 경우, 어떤 두 노드가 서로의 조건이 되기 때문에 아예 큐에 들어가지를 못하기 때문에 n 번 만큼 큐에서 꺼낼 노드가 존재하지 않게 되기 때문임 )
• 진입차수 벡터를 두고, prerequisites 을 iterate 하면서, 각 노드에 대한 진입 차수 값을 세팅한다.
• 큐에서 꺼낸 노드를 조건으로 갖는 노드들의 진입 차수에 대한 decrement를 비교적 쉽게 하기 위하여,
  • preprequisite으로부터 , 어떤 노드를 조건으로 갖는 노드들에 대한 정보를 따로 추가한다.

class Solution {
public List<Integer>[] child = new List[2001]; // i 노드를 조건으로 갖는 노드들
  public int[] cnt = new int[2001]; // 각 노드들의 진입차수를 저장하는 배열
  public LinkedList<Integer> q = new LinkedList<>();

  public int[] findOrder(int numCourses, int[][] prerequisites) {
    int[] answer = new int[numCourses];
    // init
    for (int i = 0;i<numCourses;i++){
      child[i] = new ArrayList<>();
    }
    for(int[] pair : prerequisites){
     child[pair[1]].add(pair[0]); // 어떤 노드를 조건으로 갖는 노드 정보 세팅
     cnt[pair[0]]++; // 어떤 노드의 진입차수 값
    }
    // 진입차수가 0 인 값들을 q 에 세팅한다
    for (int i =0;i<numCourses;i++){
      if(cnt[i]==0)q.add(i);
    }
    // q 에서는 numCourses 개 만큼의 노드들을 꺼낼 수 있어야 한다.
    for (int count=0;count<numCourses;count++){
      if(q.isEmpty()) return new int[0]; // numCourses 개를 꺼내기 전에 큐가 빔 -> cyclic 한 그래프 ( 두 노드가 서로를 조건으로 가짐)
      Integer first = q.pollFirst();
      answer[count] = first; 
      // first 를 조건으로 갖는 노드들에 대한 업데이트가 필요함
      for (Integer integer : child[first]) {
        cnt[integer]--;
        // 이로인해 진입차수가 0이 된 노드 -> 큐에 삽입
        if (cnt[integer]==0) q.add(integer);
      }
      
    }
    return answer;
  }

}