위상 정렬(Topological sorting)

위상 정렬이란?(What is Topological Sorting?)

---

 위상 정렬의 뜻을 검색해보면 "DAG에 대한 위상 정렬은 정점 u에서 정점 v로 가는 방향이 있는 간선이 있을 때 모든 정점 u가 모든 정점 v 앞에 오도록 정점을 정렬하는 선형 정렬"이라고 나온다. 이 말이 쉽게 와닿지 않을 수 있다. 하지만 게임의 테크트리를 생각하면 어떤 말인지 쉽게 알 수 있다. 

 우리가 게임을 하다보면 어떤 기술을 열거나 건물을 건설할 때 요구 조건이 있는 것을 한번쯤은 봤을 것이다. 그리고 요구 조건을 충족할 때만 기술을 열거나 건물을 건설할 수 있다. 이때 각 건물과 기술들이 정점이 되는 것이고 요구 조건과 관련된 건물과 기술의 관계가 간선이라고 생각하면 된다.

 

문명5의 기술표. 각 기술이 노드이고 기술과 기술을 잇는 선이 간선이다.

 

그런데 위상 정렬 앞에 DAG란 조건이 붙어있다. DAG는 Directed Acyclic Graph의 약자로 방향이 있는 비순환 그래프를 의미한다. 즉 위상 정렬은 방향이 있는 비순환 그래프에서만 적용을 할 수 있다는 의미이다. 왜 그럴까? 일단 방향이 있어야 한다는 건 다들 이해했을 것이다. 위상 정렬은 누가 먼저 오느냐를 정렬하는 알고리즘이기 때문이다. 그러면 순환이 생기면 어떻게 될까? 

 

위 그림에서 A를 방문하기 위한 조건은 C를 방문하는 것이다. 그럼 C를 먼저 방문해야 하는데 C를 방문하기 위한 조건은 B를 방문하는 것이고 B를 방문하기 위해 조건은 A를 방문하는 것이다. 즉 서로가 서로를 요구하고 있기 때문에 어떤게 먼저 올지 결정할 수 없다. 이는 운영체제의 교착상태와 같다.

 

위상 정렬 알고리즘(Topological Sorting Algorithm)

---

그럼 아래 그림을 이용해 위상 정렬을 알고리즘으로 구현해보자.

 

 먼저 그림이 어떤 의미인지 알아보자. 노드는 A부터 G까지 있고 각 노드를 방문하기 위한 요구 조건은 간선으로 표시되어 있다. 화살표의 의미는 해당 노드를 방문해야만 화살표가 가리키는 방향의 노드로 갈 수 있다는 표시이다. 즉 B->A의 의미는 B 노드를 방문해야만 A로 갈 수 있다는 의미이다. 그러면 G 노드의 방문 조건은 어떻게 될까? D, E, F를 모두 방문해야지만 G를 방문할 수 있다는 의미가 된다.

 그래프 말고도 3개의 표가 보인다. Queue는 앞으로 방문 예정인 노드들이 들어있는 queue이다. Output은 결과가 나오는 표이다. Degree는 들어오는 간선의 개수를 표시한 표이다. 이 Degree를 이용해 해당 간선에 요구 조건이 충족되었는지 확인한다. 그러면 알고리즘을 시작해보자!

 

 

먼저 방문 가능한 노드를 찾아보자. Degree에서 0이 되는 노드를 찾아보면 B와 E가 0이 되는 것을 알 수 있고 이를 통해 B와 E 노드가 방문 가능하다는 것을 알 수 있다. 방문 가능한 노드는 Queue에 저장한다. 그리고 각 노드와 연결된 노드들의 Degree를 하나씩 줄여준다. B의 경우 A와 C가 연결되어 있으므로 A와 C의 Degree를 각각 1개씩 줄여준다. 줄여준 결과가 0과 같디에 A와 C를 Queue에 넣어준다.

 

방문한 B와 E는 Queue에서 제거하고 Output에 출력한다. 다음으로 A와 C를 방문한다. A와 C랑 연결된 D의 degree를 줄여준다. 그 결과가 0이기 때문에 Queue에 D를 저장한다. 방문한 A와 C는 Output으로 출력한다.

 

다음으로 D를 방문한다. D와 연결된 F와 G의 degree를 하나씩 줄여준다. 줄여준 결과가 0인 F를 Queue에 넣어준다.

방문한 D는 Output에 출력한다.

 

다음으로 F를 방문한다. F와 연결된 G의 degree를 하나 줄여주고 그 결과가 0이기 때문에 Queue에 저장해 준다.

방문한 F는 Output에 출력한다.

 

마지막에 있던 G를 방문하고 G와 연결된 노드가 없기 때문에 Degree 계산은 넘어간다. 방문했던 G는 output에 출력한다. 이제 큐가 비었으니 알고리즘을 종료한다.

 

위상 정렬 알고리즘 코드(Topological Sorting Algorithm Code)

---

필자는 자바로 해당 알고리즘을 구현헀다.

 

입력은 아래와 같이 한다.

1. 첫 줄에는 노드의 개수와 간선의 개수를 입력한다.

2. B -> A로 간선이 설정되어있으면 B A로 입력한다.

3. 간선의 개수만큼 2 과정을 반복한다.

 

입력:

7 8
B A
B C
A D
C D
D F
D G
E G
F G

 

결과:

BEACDFG

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 노드 개수와 간선 개수 입력
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 노드 연결 관계를 저장하는 리스트
        List<List<Integer>> nodeList = new ArrayList<>();
        // 들어오는 간선의 수를 저장하는 배열
        int[] degreeArr = new int[N + 1];


        // 리스트 초기화
        for (int i = 0; i <= N; i++) {
            nodeList.add(new ArrayList<>());
        }

        // 각 노드의 간선 수 계산 및 노드 관계 설정
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int start = st.nextToken().toCharArray()[0] - 64;
            int end = st.nextToken().toCharArray()[0] - 64;

            nodeList.get(start).add(end);
            degreeArr[end]++;
        }

        // 방문 예정 큐
        Queue<Integer> q = new LinkedList<>();

        // 처음으로 방문할 노드를 큐에 저장
        for (int i = 1; i < degreeArr.length; i++) {
            if (degreeArr[i] == 0) {
                q.offer(i);
            }
        }

        StringBuilder sb = new StringBuilder();

        // 큐가 빌 때까지 방문
        while (!q.isEmpty()) {
            Integer poll = q.poll();

            sb.append((char) (poll + 64));

            // 방문한 큐와 연결된 노드의 간선 개수 줄이기
            for (int vertex: nodeList.get(poll)) {
                degreeArr[vertex]--;

                // 만약 줄인 간선의 개수가 0이면 방문 예정 큐에 해당 노드 넣어주기
                if (degreeArr[vertex] == 0) {
                    q.offer(vertex);
                }
            }
        }

        System.out.println(sb.toString());
    }
}