[알고리즘] 위상 정렬

1. 개념

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 

이렇게 구한 노드 순서는 해당 순서의 노드가 처리되기 위해서는 그 노드보다 앞에 있는 노드가 처리되어야 함을 의미한다. 즉, 반약 위상 정렬의 결과가 1 2 3 4 5 일 때, 2가 처리되기 위해서는 무조건 1이 처리되어야 하는 것이고, 5가 처리되기 위해서는 무조건 1234가 처리 되어 있어야 하는 것이다.

 

2. 특징

• 항상 유일한 값으로 정렬되지 않는다.
• 시간 복잡도는 O(노드 수 + 에지 수) 이다.

 

3. 원리

• 진입 차수를 이용한다
  • 진입 차수는 자기 자신을 가리키는 에지의 개수를 의미한다.
  • 진입 차수가 0이라는 것은 해당 노드는 아무 것에도 의지하지 않는다는 것을 의미한다. 그래서 진입 차수가 0인 것을 먼저 정렬한다. -- 1
  • 그리고 위에서 정렬한 결과는 이미 완료된 것이니, 정렬된 노드가 가리키고 있던 노드들의 진입차수를 1씩 줄인다. -- 2
  • 1과 2를 반복해서 정렬을 진행하다가, 진입차수가 모두 0이 되면 종료한다.

 

4. 구현

// inDegree는 각 노드별 진입차수를 담고 있는 배열
// arr은 연결리스트 정보

public static void topoSort(){
    Queue<Integer> queue = new LinkedList<>();

    for(int i = 1; i<=N; i++){
        if(inDegree[i] == 0){
            queue.offer(i);
        }
    }

    while(!queue.isEmpty()){
        int now = queue.poll();
        System.out.print(now + " ");
        for(int next : arr.get(now)){
            inDegree[next]--;
            if(inDegree[next] == 0){
                queue.offer(next);
            }
        }
    }
}

 

5. 관련 문제

백준 2252

GitHub - Lee-Min-Jung/coding_test_practice

백준 1516

GitHub - Lee-Min-Jung/coding_test_practice

백준 1948

GitHub - Lee-Min-Jung/coding_test_practice