[LeetCode] 210. Course Schedule II - 위상정렬(TopologicalSort) JAVA

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

코드설명

위상정렬(TopologicalSort)을 활용합니다.

 

DFS를 활용하여 위상정렬을 구현하는 것은 어렵지 않습니다.

중요한점은, 어디에서 시작하든지 간에 위상정렬을 구할 수 있기에, inDegree를 계산할 필요가 없다는점을 유의합니다.

그렇게 처리함으로써, 더 깊은 이해가 가능해집니다.

 

하지만, 사이클 판명 부분에서 어려움을 겪었습니다.

예시 2번의, order : [0, 2, 1, 3] 의 정렬을 구했다고 가정하겠습니다.

이때 이러한 위상 정렬이 의미하는 것은, 순서대로 그래프가 DAG(Directed ACyclic Graph)의 순서를 나타냄을 알 수 있습니다.

그러므로, 뒤의 순서에 있는 그래프의 정점이 앞에 있는 그래프를 바라보는것은, "사이클"이 존재한다고 할 수 있습니다.

 

아래의 코드를 통해, 사이클일 경우 빈 배열을 반환합니다.

for(int i=0; i<NumCourses; i++){
	for(int j=i+1; j<NumCourses; j++){
    	ArrayList<Integer> graphOfJ = graph.get(order.get(j));
        for(int k=0; k<graphOfJ.size(); k++){
        	if(order.get(i) == graphOfJ.get(k)){
            	return new ArrayList<Integer>();
            }
        }
    }
}

 

코드

정답코드1입니다.

class Solution {
    boolean[] seen;
    ArrayList<ArrayList<Integer>> graph;
    ArrayList<Integer> order;
    int NumCourses;
    int[][] Prerequisites;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        NumCourses = numCourses;
        Prerequisites = prerequisites;
        graph = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<numCourses; i++){
            graph.add(new ArrayList<Integer>());
        }
        for(int i=0; i<Prerequisites.length; i++){
            int a = Prerequisites[i][0];
            int b = Prerequisites[i][1];
            graph.get(b).add(a);
        }
        List<Integer> sorted = topologicalSort();
        int[] answer = new int[sorted.size()];
        for(int i=0; i<sorted.size(); i++){
            answer[i] = sorted.get(i);
        }
        return answer;
    }

    void DFS(int here){
        seen[here] = true;
        ArrayList<Integer> connected = graph.get(here);
        for(int i=0; i<connected.size(); i++){
            if(seen[connected.get(i)] == false){
                DFS(connected.get(i));
            }
        }
        order.add(here);
    }

    List<Integer> topologicalSort(){
        seen = new boolean[NumCourses];
        order = new ArrayList<Integer>();
        for(int i=0; i<NumCourses; i++){
            if(seen[i] == false){
                DFS(i);
            }
        }
        Collections.reverse(order);
        for(int i=0; i<NumCourses; i++){
            for(int j=i+1; j<NumCourses; j++){
                //j번째가 i를 바라보는경우가 있을경우 실패입니다.
                ArrayList<Integer> graphOfJ = graph.get(order.get(j));
                for(int k=0; k<graphOfJ.size(); k++){
                    if(graphOfJ.get(k) == order.get(i)){
                        return new ArrayList<>();
                    }
                }
            }
        }
        return order;
    }
}

 

처음에 작성한 오답크도1입니다.

정답이 맞아보이지만,

numCourses = 3, prerequisite = [[1, 0], [1, 2], [0, 1]] 에 대해서 일종의 사이클이 발생하여 [] 를 반환해야합니다.

보시면 알겠지만, 1번 Course 수업을 듣기 위해서는 0번 수업을 듣고 들어야하고, 0번 수업을 듣기 위해서는 1번 수업을 듣고 들어야 합니다. 불가능한 경우라는 것을 알 수 있습니다.

class Solution {
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    int[] inDegree;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        visited = new boolean[numCourses];
        for(int i=0; i<numCourses; i++){
            graph.add(new ArrayList<Integer>());
        }

        inDegree = new int[numCourses];
        for(int i=0; i<prerequisites.length; i++){
            int a = prerequisites[i][0];//진입차수 위치
            int b = prerequisites[i][1];//진출차수 위치
            graph.get(b).add(a);
            inDegree[a] += 1;
        }

        int startIdx = 0;
        for(int i=0; i<inDegree.length; i++){
            //inDegree는 
            if(inDegree[i] == 0){
                startIdx = i;
                DFS(startIdx);
            }
        }
        
        Collections.reverse(ret);
        int[] answer = new int[ret.size()];
        int idx = 0;
        for(int v : ret){
            answer[idx++] = v;
        }
        return answer;
    }
    List<Integer> ret = new ArrayList<Integer>();
    boolean[] visited;
    public void DFS(int idx){
        ArrayList<Integer> node = graph.get(idx);
        for(int i=0; i<node.size(); i++){
            int next = node.get(i);
            if(visited[next] == false){
                visited[next] = true;
                DFS(next);
            }
        }
        ret.add(idx);
    }
}