[LeetCode] 207. Course Schedule

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

각 노드를 순회하며, 노드로부터 사이클이 형성되는지 판단하면 된다.
각 course에 대해 사이클 존재 여부는 backtracking으로 판단할 수 있다.

Algorithm

주어진 course dependency에 따라 인접리스트로 그래프를 생성한다.
Hashmap이나 dictionary로 구현할 수 있다. 인접리스트의 각 entry는 node의 index와, 그 node에 이어진 neighbor 노드들로 구성된다.
그래프에서 각 node(course)를 순회하며 해당 노드로부터 cycle을 형성할 수 있는지 검사한다.
backtracking으로 cycle을 확인한다. 이미 방문한 노드를 표시해놓고, 이미 방문한 노드를 또 방문한다면 cycle이 존재하는 것이다.

구현

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> adjacencyList = new HashMap<>();
        
        for(int[] course: prerequisites) {
            int prevCourse = course[0];
            int nextCourse = course[1];
            if(adjacencyList.containsKey(prevCourse)) {
                adjacencyList.get(prevCourse).add(nextCourse);
            }
            else {
                List<Integer> nextList = new ArrayList<>();
                nextList.add(nextCourse);
                adjacencyList.put(prevCourse, nextList);
            }
        }
        
        boolean[] visited = new boolean[numCourses];
        for(int currCourse=0; currCourse<numCourses; currCourse++) {
            if(this.isCyclic(adjacencyList, currCourse, visited))
                return false;
        }
        return true;
    }
    
    protected boolean isCyclic
        (HashMap<Integer, List<Integer>> adjacencyList, int currCourse, boolean[] visited) {
        if(visited[currCourse]) return true;
        
        if (!adjacencyList.containsKey(currCourse))
            return false;

        visited[currCourse] = true;
        
        boolean ret = false;
        for(int nextCourse : adjacencyList.get(currCourse)) {
            ret = this.isCyclic(adjacencyList, nextCourse, visited);
            if(ret)
                break;
        }
        
        visited[currCourse] = false;
        return ret;
    }
}

2. Postorder DFS (Depth-First Search)

1번의 backtracking 풀이에서는 효율적이지 않게 특정 노드들을 여러 번 방문하고 있다.

예를 들어, 위의 그래프 처럼 node들이 일련의 체인을 이루고 있을 때, backtracking 알고리즘은 0번 노드에 cycle이 없다는 것을 발견한 후에도, 0번에 연결된 다른 노드들에 대해서 다시 탐색을 수행한다. downstream(후손 노드들)에 대해서 같은 check를 중복으로 할 필요가 없다.

Algorithm

위의 backtracking algorithm에 다른 bitmap을 추가하여 간단하게 postorder DFS를 구현할 수 있다. (checked[node_index]는 이미 해당 노드를 cyclic check 했음을 나타낸다.)

구현

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> adjacencyList = new HashMap<>();
        
        for(int[] course: prerequisites) {
            int prevCourse = course[0];
            int nextCourse = course[1];
            if(adjacencyList.containsKey(prevCourse)) {
                adjacencyList.get(prevCourse).add(nextCourse);
            }
            else {
                List<Integer> nextList = new ArrayList<>();
                nextList.add(nextCourse);
                adjacencyList.put(prevCourse, nextList);
            }
        }
        
        boolean[] visited = new boolean[numCourses];
        boolean[] checked = new boolean[numCourses];
        for(int currCourse=0; currCourse<numCourses; currCourse++) {
            if(this.isCyclic(adjacencyList, currCourse, checked, visited))
                return false;
        }
        return true;
    }
    
    protected boolean isCyclic
        (HashMap<Integer, List<Integer>> adjacencyList, 
         int currCourse, boolean[] checked, boolean[] visited) {
        if(checked[currCourse]) return false;
        if(visited[currCourse]) return true;
        
        if (!adjacencyList.containsKey(currCourse))
            return false;

        visited[currCourse] = true;
        
        boolean ret = false;
        for(int nextCourse : adjacencyList.get(currCourse)) {
            ret = this.isCyclic(adjacencyList, nextCourse, checked, visited);
            if(ret)
                break;
        }
        
        visited[currCourse] = false;
        checked[currCourse] = true;
        return ret;
    }
}

3. Topological Sort

들을 수 있는 수업의 개수인 numCourses가 주어지고, 선수 과목 쌍이 주어지면, 모든 수업을 수강할 수 있는지 그 여부를 반환하는 문제이다.
즉, 방향이 있는 그래프에서 cycle이 있다면 false, 없고 모든 노드를 방문할 수 있다면 true를 반환하는 문제로 치환할 수 있고, 바로 위상정렬을 하는 문제이다.

위상정렬

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

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

위상정렬의 결과

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

Algorithm

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

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

구현

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacencyList = new ArrayList<>();
        Queue<Integer> result = new LinkedList<>();
        Queue<Integer> queue = new LinkedList<>();
        int[] indegree = new int[numCourses];
        
        for(int i=0; i<numCourses; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        
        for(int i=0; i<prerequisites.length; i++) {
            int start = prerequisites[i][0];
            int end = prerequisites[i][1];
            adjacencyList.get(start).add(end);
            indegree[end]++;
        }
        
        for(int i=0; i<numCourses; i++) {
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while(!queue.isEmpty()) {
            int currNode = queue.poll();
            result.offer(currNode);
            
            for(Integer child : adjacencyList.get(currNode)) {
                indegree[child]--;
                
                if(indegree[child] == 0)
                    queue.offer(child);
            }
        }
        if(result.size() == numCourses) return true;
        return false;
    }
}