[알고리즘] 순서대로 작업하는 위상 정렬(Topology Sort)

 

 

✅ 위상정렬이란?

: 순서가 정해져있는 작업 을 차례대로 진행해야할 때, 그 순서를 결정해주기 위해 사용하는 알고리즘입니다. 사이클이 없는 방향 그래프(DAG)의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미합니다.

 

그렇다면 순서가 있는 작업의 예시를 통해 정확하게 이해하도록 하겠습니다.

 

 위 그래프의 흐름을 보면 '조건'으로 해석할 수 있습니다. '튀기기'전에 반드시 '닭 손질하기'를 수행해야하고, 양념에 버무리기 전에 '후라이드'와 '양념 만들기' 작업을 수행해야 합니다. 위와 같이 여러 개의 순서가 정해져있을 때, 조건에 부합하는 일직선상의 순서를 찾아보겠습니다.

 

위상정렬 순서:
닭 손질하기 -> 튀기기 -> 후라이드 -> 양념 만들기 -> 양념에 버무리기 -> 무많이 -> 반반 무많이

 

 이렇게 정렬한다면 개발자들은 정상적으로 '반반 무많이'를 먹을 수 있습니다! 물론, 다른 경우의 수도 있기 때문에 위상 정렬의 결과는 여러 개의 답이 존재할 수 있습니다. 반면에, 사이클이 발생하는 경우, 위상 정렬을 수행할 수 없게 됩니다.

 

 위와 같은 그래프가 있는 경우, 위상 정렬의 시작점을 찾을 수 없고, 작업의 순서를 정의할 수 없기 때문에 위상 정렬을 수행할 수 없습니다.

 

✅ 위상정렬의 결과

 위상 정렬 알고리즘은 2가지 결과를 도출할 수 있습니다.

 

1. 현재 그래프가 위상 정렬이 가능한지
2. 위상정렬이 가능하다면 작업의 순서 or 결과는 무엇인지

위상 정렬을 수행하는 알고리즘으로는 스택과 큐를 이용하는 방식이 있습니다. 큐를 이용하는 경우, 알고리즘 순서는 아래와 같습니다.

 

[ 위상정렬 과정 ]

1. 진입차수가 0인 정점을 모두 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거
3. 간선을 제거한 후, 진입차수가 0이 된 정점을 다시 큐에 삽입
4. 큐가 빌 때까지 2~3번을 반복, 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과입니다.

 

간단한 Java 코드와 출력 결과를 확인해보겠습니다.

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


//     1         2         3          4          5          6        7
// 닭 손질하기, 튀기기, 양념 만들기, 후라이드, 양념 버무리기, 무많이, 반반 무많이

public class TopologySort {
    static int[] preOrderCnt;
    static List<Integer>[] orders = new ArrayList[8];
    static Map<Integer, String> orderTable = new HashMap<>();

    public static void getTopologySortResult() {
        Queue<Integer> que = new LinkedList<>();

        // (1)진입차수가 0인 정점을 큐에 삽입
        for(int i=1; i<8; i++) {
            if(preOrderCnt[i] == 0) que.offer(i);
        }

        // (4) 큐가 빌 때까지 반복
        while(!que.isEmpty()) {
            int current = que.poll();
            System.out.println(current+": "+orderTable.get(current));

            // (2)연결된 간선제거
            for(int next: orders[current]) {
                preOrderCnt[next] -= 1;

                // (3)만약, 다음 정점의 진입차수가 0인 경우, 큐에 삽입
                if(preOrderCnt[next] == 0) {
                    que.offer(next);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        settingOrders();
        settingOrderTable();
        getTopologySortResult();
    }

    public static void settingOrderTable() {
        orderTable.put(1, "닭 손질하기");
        orderTable.put(2, "튀기기");
        orderTable.put(3, "양념 만들기");
        orderTable.put(4, "후라이드");
        orderTable.put(5, "양념 버무리기");
        orderTable.put(6, "무많이");
        orderTable.put(7, "반반 무많이");
    }

    public static void settingOrders() {
        for(int i=1; i<8; i++)
            orders[i] = new ArrayList<>();

        preOrderCnt = new int[8];
        orders[1].add(2);
        orders[1].add(3);
        orders[2].add(4);
        orders[3].add(5);
        orders[4].add(5);
        orders[3].add(7);
        orders[5].add(7);
        orders[6].add(7);

        preOrderCnt[2] += 1;
        preOrderCnt[3] += 1;
        preOrderCnt[4] += 1;
        preOrderCnt[5] += 2;
        preOrderCnt[7] += 3;
    }
}

 

 

 위상 정렬의 시간 복잡도는 정점의 갯수 + 간선의 갯수만큼 소요되는 O(V+E)가 됩니다.

 

👍 References

https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting

https://m.blog.naver.com/ndb796/221236874984