[위상 정렬 (Topology Sort)] 선수과목 순서 정렬 알고리즘

위상 정렬 (Topology Sort)

• 유향 그래프의 정점들의 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
• 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해 주는 알고리즘이다.
• 위상 정렬을 가장 잘 설명해 줄 수 있는 예로 교육과정의 선수과목(prerequisite) 구조를 예로 들 수 있다.
• 만약 특정 수강 과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다.

---

• 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다.
• 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다.
• 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다.
• 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다.

---

• 위상 정렬이 가능한지 여부
  • 사이클 발생 여부 확인가능
• 가능하다면 정렬된 결과
  => 사이클 없음
  

사이클 발생 여부를 확인할 수 있다는 점을 활용해 볼 수도 있겠다

시간복잡도 : $O(V+E)$

---

활용 예

• 작업 스케줄링, 종속성 처리
  • npm 등의 패키지 매니저
  • 운영체제의 프로세스 스케줄링 등
• 사이클 감지
  • 사이클이 존재하는 그래프는 위상정렬이 반드시 실패한다는 점을 이용
    => 데드락 등 교착 상태에서의 사이클을 감지

---

구현방식

• BFS를 이용한 구현 (Kahn 알고리즘) - 이해, 구현 쉬움
• DFS를 이용한 구현

BFS 사용
0. 모든 정점의 진입차수를 계산한다.
1. 진입 차수가 0인 노드(시작점)를 큐에 모두 넣는다.
2. 큐에서 진입 차수가 0인 노드를 꺼내어 자신과 인접한 노드의 간선을 제거한다.
-> 인접한 노드의 진입 차수를 1 감소시킨다.
3. 간선 제거 후 진입 차수가 0이 된 노드를 큐에 넣는다.

• 큐가 공백 큐 상태가 될 때까지 2-3 작업을 반복한다.
  • 모든 노드가 처리되지 않았다면 사이클 발생
  • 모든 노드가 다 처리되었다면 위상 정렬 완성

---

• 방문처리를 안 해도 된다.
• 순서출력을 큐에 넣을 때, 뺄 때 아무데나 해도 된다.

---

예시 코드 (Kahn 알고리즘)

JAVA

import java.io.*;
import java.util.*;

class Main {
    
    static int N, M;
    static List<Integer>[] graph;
    static int indegrees[];
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        graph = new ArrayList[N+1];
        indegrees = new int[N+1];       // 진입차수 수
        for (int n=1; n<=N; n++) {
            graph[n] = new ArrayList<Integer>();
        }
        
        for (int m=0; m<M; m++) {        // 선후관계 입력
            st = new StringTokenizer(br.readLine());
            int small = Integer.parseInt(st.nextToken());
            int tall = Integer.parseInt(st.nextToken());
            graph[small].add(tall);
            indegrees[tall]++;          // 진입차수 수 증가
        }
        
        bfs();
        
        System.out.println(sb);

    }
    
    static void bfs() {
        Deque<Integer> que = new ArrayDeque<>();
        // 진입차수가 0인 것들을 인큐
        for (int n=1; n<=N; n++) {
            if (indegrees[n] == 0) {
                que.offer(n);
            }
        }
        
        while (!que.isEmpty()) {
            // 디큐
            int now = que.poll();
            sb.append(now).append(" ");
            
            for (int num : graph[now]) {
                indegrees[num]--;
                if (indegrees[num] == 0) {
                    que.offer(num);
                }
            }
        }
    }
    
}

백준 - 줄 세우기(2252)
위 코드를 제출하면 정답 처리가 된다.

---

생각보단 그리 구현이 어렵지 않다