기억하고싶은것들

위상 정렬(Topological Sorting)

순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주는 데 사용되는 알고리즘

(일을 하는 순서를 찾는 알고리즘)

DAG( Directed Acyclic Graph ) -방향이 존재하고, 사이클이 존재하지 않는 그래프에서 사용 가능 

방향이 존재하는 그래프에서 사용하므로 

진입 차수를 사용하여 알고리즘을 구현한다.

진입 차수(indegree)

진입 차수(indegree) : 특정한 노드로 들어오는 간선의 개수

위의 그림에서 7 -> 5에서

5의 진입 차수는 1이다

7의 집입 차수는 0이다

위상 정렬 동작 과정

각 노드의 진입 차수를 구한다. 

진입 차수가 0 인 노드를 큐에 넣는다.

큐에 있는 노드의 간선을 제거 

 - ( 해당 간선을 진입 차수로 둔 노드의 진입 차수도 제거 )

 - 제거 과정에 진입 차수가 0이 된 노드는 큐에 추가 

    public boolean topologicalSorting(int numCourses, int[][] prerequisites) {

        List<Integer>[] graph = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] pre : prerequisites) { // 노드별 진입차수 계산
            inDegree[pre[0]]++;
            graph[pre[1]].add(pre[0]);
        }
        for (int i = 0; i < inDegree.length; i++) { // 진입차수가 0인 노드 선별
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) { // 큐의 노드 간선 제거 및 진입차수 제거 
            int idx = queue.poll();

            for (int tmp : graph[idx]) {
                inDegree[tmp]--;
                if (inDegree[tmp] == 0) {
                    queue.offer(tmp);
                }
            }
        }

        return Arrays.stream(inDegree).sum() == 0;
    }

관련 문제

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