[Algo] 위상 정렬(Topological Sort)

• 위상정렬 이란?

  그래프와 관련된 알고리즘 중의 하나로 선후관계가 정의된 그래프 구조에서 정렬을 하기 위해 사용합니다.
  

위와 같은 그래프가 있을 때, 노드마다 연결된 간선에 방향이 있고 어떤 특정 노드를 방문하기 위해서는 해당 노드에 진입 가능한 노드들을 모두 방문한 후에 방문이 가능하다고 가정해보겠습니다.

그렇다면 현재 그래프의 선후관계는 다음과 같습니다.

이러한 선후관계가 존재할 때, 노드를 방문하는 순서를 찾아야 한다면 위상 정렬을 사용할 수 있습니다.

또한 예를 들어 그래프가 어떠한 물건의 생산 흐름이라고 하면 각각의 노드들이 특정한 작업이 되고, 이때 작업의 순서를 구해야 한다면 위상 정렬을 사용할 수 있습니다.

** 단 그래프가 순환관계에 있다면 위상정렬을 사용할 수 없습니다. 즉, 비순환 그래프 DAG(Directed Acyclic Graph)이어야 사용할 수 있습니다.

• 위상정렬 순서

1. 그래프의 각 노드들의 진입 차수 테이블 생성 및 진입 차수 계산
2. 진입 차수가 0인 노드 큐에 넣기 (이때 어떤 노드 먼저 시작하던지 관계없음)
3. 큐에서 노드를 하나 꺼낸 후 꺼낸 노드와 간선으로 연결된 노드들의 진입 차수 감소 (진입 차수 테이블 갱신)
4. 진입 차수 테이블을 갱신 후 진입 차수의 값이 0인 노드가 있다면 큐에 넣기 (없으면 아무것도 안 함)
5. 3~4번의 순서를 큐에 더 이상 아무것도 없을 때까지 반복

위와 같은 순서로 위상 정렬(Topological Sort)은 수행되며, 모든 순서가 끝났는데도 진입 차수가 0이 아닌 노드가 있다면 그래프 내에서 순환이 존재한다고 볼 수 있습니다.

1. 그래프의 각 노드들의 진입 차수 테이블 생성 및 진입 차수 계산

위의 그림은 앞에서 봤던 예시 그래프의 선후관계를 고려해서 진입 차수 테이블을 생성한 상태입니다.
앞에서 선후관계를 나타냈던 테이블의 노드 개수가 결국 진입 차수와 같은 의미 입니다.

2. 진입 차수가 0인 노드 큐에 넣기 (이때 어떤 노드 먼저 시작하던지 관계없음)

진입 차수가 0인 1번노드와 7번노드를 큐에 넣습니다.

3. 큐에서 노드를 하나 꺼낸 후 꺼낸 노드와 간선으로 연결된 노드들의 진입 차수 감소 (진입 차수 테이블 갱신)

우선 큐에서 1번 노드를 꺼내고 인접한 노드들을 찾습니다. 그 후 1번노드와 연결되어있는 노드들의 진입차수를 하나 차감합니다.

4. 진입 차수 테이블을 갱신 후 진입 차수의 값이 0인 노드가 있다면 큐에 넣기 (없으면 아무것도 안 함)

진입차수를 차감하였으면 차감된 노드들의 진입차수를 확인하고 만약 진입차수가 0이라면 큐에 저장합니다.

• 위상 정렬(Topological Sort)을 Java코드로 구현

package study.blog.codingnojam.algorithm;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Study_topologicalSort {

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

        // 위상정렬 결과를 출력할 객체
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 위상정렬에 사용할 진입차수 저장 배열
        // 길이가 9인 이유는 인덱스를 1부터 사용하기 위해서입니다.
        int[] edgeCount =new int[9];

        // 위상정렬에 사용할 그래프 2차원 리스트로 구현
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 그래프 각 노드별 인접한 노드정보 초기화
        graph.get(1).add(2);
        graph.get(1).add(4);
        graph.get(2).add(5);
        graph.get(2).add(6);
        graph.get(3).add(6);
        graph.get(4).add(2);
        graph.get(4).add(8);
        graph.get(7).add(3);
        graph.get(8).add(6);

        // 진입차수 테이블 초기화
        edgeCount[2] = 2;
        edgeCount[3] = 1;
        edgeCount[4] = 1;
        edgeCount[5] = 1;
        edgeCount[6] = 3;
        edgeCount[8] = 1;

        // 위상정렬에 사용할 큐
        Queue<Integer> q = new LinkedList<>();

        // 진입차수가 0인 값 큐에 넣기
        for (int i = 1; i < edgeCount.length; i++) {
            if (edgeCount[i] == 0) {
                q.offer(i);
            }
        }

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            // 큐에서 노드번호 꺼내기
            int nodeNo = q.poll();

            // 꺼낸 노드번호 정렬 결과값에 저장
            bw.write(String.valueOf(nodeNo) + " ");

            // 꺼낸 노드의 인접한 노드들 찾기
            List<Integer> list = graph.get(nodeNo);

            // 인접한 노드의 개수만큼 반복문 실행
            for (int i = 0; i < list.size(); i++) {
                // 인접한 노드 진입차수 갱신
                edgeCount[list.get(i)] -- ;
                // 갱신된 노드의 진입차수가 0이면 큐에 노드 넣기
                if (edgeCount[list.get(i)] == 0) {
                    q.offer(list.get(i));
                }
            }
        }

        // 위상정렬 수행 결과 값 출력
        bw.flush();
    }
}

예제 코드에서는 그래프를 초기화할 때 값을 직접 리스트에 add 해주었지만 실제 코딩 테스트에서는 주어진 입력값을 받아서 초기화를 하셔야 합니다.