210. Course Schedule II

문제 링크: https://leetcode.com/problems/course-schedule-ii/

Solution

들을 수 있는 수업의 개수인 numCourses가 주어지고, 선수 과목 쌍이 주어지면, 모든 수업을 수강할 수 있는지 그 여부를 반환하는 문제이다.
즉, 그래프가 DAG(Directed Acyclie Graph)인지 판단하는 문제이며, cycle의 존재 여부를 판단하는 문제로 치환할 수 있다.

즉, 방향이 있는 그래프에서 cycle이 있다면 false, 없고 모든 노드를 방문할 수 있다면 true를 반환하는 문제로 치환할 수 있고, 바로 위상정렬을 하는 문제이다.

Topological Sort

위상정렬

'순서가 정해져 있는' 작업을 차례로 수행해야 할 때, 그 순서를 결정하는 알고리즘이다.
위상정렬을 사용하면 방향 그래프에서 다양한 조건들이 얽혀있을 때 일직선 상의 한 가지 경로를 찾아낼 수 있다.

• 여러 개의 답이 존재 가능하다.
• Directed Acyclic Graph(DAG)에만 적용이 가능하다. (방향이 있고 싸이클이 없는 그래프)
  cycle이 있다면 시작점을 찾을 수 없다.

위상정렬의 결과

1. 현재 그래프가 위상정렬이 가능한지 (cycle이 존재하는지)
2. 위상정렬이 가능하다면 그 결과는 무엇인지

Algorithm

1. 진입차수(특정 노드로 들어오는 다른 노드의 개수)가 0인 노드를 큐에 삽입한다.
2. 큐에서 원소를 꺼내, 그에 연결된 간선을 모두 제거한다.
   이 때, 간선을 제거한 후 노드들의 진입차수를 갱신한다.
3. 진입차수가 0이된 노드들을 다시 큐에 삽입한다.
4. 큐가 빌 때까지 2~3의 과정을 반복한다.

결과: 모든 원소를 방문 했다면 큐에서 꺼낸 결과가 위상정렬 결과 (모든 원소 방문 전 큐가 비었다면 사이클이 존재)

구현

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adjacencyList = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        int[] result = new int[numCourses];
        int[] indegree = new int[numCourses];
        for(int i=0; i<numCourses; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        
        for(int course[] : prerequisites) {
            int prevCourse = course[1];
            int nextCourse = course[0];
            adjacencyList.get(prevCourse).add(nextCourse);
            indegree[nextCourse]++;
        }
        
        for(int course=0; course<numCourses; course++) {
            if(indegree[course]==0) {
                queue.offer(course);
            }
        }
        
        int resultIndex = 0;
        while(!queue.isEmpty()) {
            Integer currCourse = queue.poll();
            result[resultIndex++] = currCourse;
            for(int course: adjacencyList.get(currCourse)) {
                indegree[course]--;
                if(indegree[course] == 0) {
                    queue.offer(course);
                }
            }
        }
        
        if(resultIndex != numCourses) return new int[]{};
        return result;
    }
}