알고리즘 - 위상정렬

위상 정렬(Topological Sort)이란?

위상 정렬(Topological Sort)은 방향 그래프에서 노드들을 선후관계를 따져 정렬하는 알고리즘입니다. 이 알고리즘은 DAG(Directed Acyclic Graph), 즉 사이클이 없는 방향 그래프에서만 동작합니다. 위상 정렬은 작업의 순서가 중요한 문제에서 자주 사용됩니다. 예를 들어, 프로젝트 관리에서 작업 간의 의존 관계를 정의하고, 작업을 어떤 순서로 수행해야 하는지를 결정할 때 사용할 수 있습니다.

위상 정렬의 주요 개념

1. 방향 그래프: 그래프에서 간선이 방향을 가지며, 노드 간의 관계가 단방향인 그래프입니다.
2. 사이클 없음: 그래프 내에 자기 자신으로 돌아오는 경로가 없어야 합니다. 사이클이 존재하면 위상 정렬을 할 수 없습니다.
3. 진입 차수: 특정 노드로 들어오는 간선의 수를 의미합니다.

위상 정렬의 진행 과정

1. 진입 차수 계산: 그래프의 각 노드에 대해 진입 차수를 계산하여 테이블을 만듭니다.
2. 초기화: 진입 차수가 0인 노드들을 큐에 넣습니다.
3. 큐 처리:
   • 큐에서 노드를 하나 꺼내고 결과 리스트에 추가합니다.
   • 그 노드와 연결된 모든 노드의 진입 차수를 1씩 감소시킵니다.
   • 진입 차수가 0이 된 노드를 큐에 추가합니다.
4. 반복: 큐가 빌 때까지 3번 과정을 반복합니다.
5. 결과 확인: 모든 노드를 방문했는지 확인합니다. 만약 진입 차수가 0이 아닌 노드가 남아있다면, 순환 구조가 있어 위상 정렬이 불가능하다는 것을 의미합니다.

Java로 구현한 위상 정렬

아래는 Java를 이용해 위상 정렬을 구현한 코드입니다. 이 코드는 큐를 사용하여 위상 정렬을 수행합니다.

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));

        // 진입 차수 테이블, 인덱스를 1부터 사용하기 위해 길이 9로 설정
        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;

        // 큐 초기화 및 진입 차수가 0인 노드 추가
        Queue<Integer> q = new LinkedList<>();
        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)]--; // 인접 노드의 진입 차수 감소
                if (edgeCount[list.get(i)] == 0) {
                    q.offer(list.get(i)); // 진입 차수가 0이 된 노드를 큐에 추가
                }
            }
        }

        bw.flush();
    }
}

위상 정렬의 작동 원리 예시

아래 예시를 통해 위상 정렬이 어떻게 동작하는지 단계별로 설명하겠습니다.

예시 그래프

 

이 그래프는 8개의 노드를 가지고 있으며, 각 노드는 특정 작업을 의미합니다. 위상 정렬을 통해 작업을 수행하는 순서를 구해보겠습니다.

1. 진입 차수 테이블 생성

우선 각 노드의 진입 차수를 계산합니다. 예를 들어, 2번 노드는 1번과 4번 노드에서 들어오는 간선이 있으므로 진입 차수가 2가 됩니다.

• 1번: 0
• 2번: 2
• 3번: 1
• 4번: 1
• 5번: 1
• 6번: 3
• 7번: 0
• 8번: 1

2. 진입 차수가 0인 노드를 큐에 추가

진입 차수가 0인 노드인 1번과 7번을 큐에 추가합니다.

3. 큐에서 노드를 꺼내고 인접 노드의 진입 차수 감소

큐에서 1번 노드를 꺼내고, 1번과 연결된 2번과 4번 노드의 진입 차수를 각각 1 감소시킵니다. 그 결과, 4번 노드의 진입 차수가 0이 되어 큐에 추가합니다.

• 큐: [7, 4]
• 결과: [1]

같은 방식으로 큐에서 7번을 꺼내고, 7번과 연결된 3번 노드의 진입 차수를 감소시킵니다. 그 결과, 3번의 진입 차수가 0이 되어 큐에 추가됩니다.

• 큐: [4, 3]
• 결과: [1, 7]

4. 큐가 빌 때까지 반복

이 과정을 큐가 빌 때까지 반복합니다. 큐에서 노드를 하나씩 꺼내고, 그 노드와 연결된 모든 노드의 진입 차수를 1씩 감소시킵니다. 진입 차수가 0이 된 노드는 큐에 추가됩니다.

5. 최종 결과

모든 노드를 큐에서 꺼내면 위상 정렬이 완료됩니다. 이 예시에서는 다음과 같은 순서로 노드를 방문할 수 있습니다:

• 최종 결과: 1 -> 7 -> 4 -> 3 -> 2 -> 8 -> 5 -> 6

이 순서는 작업의 선후관계를 고려한 작업 순서입니다. 이 순서 외에도, 예를 들어 5번과 6번 노드의 순서를 바꾸는 등 다양한 위상 정렬 결과가 나올 수 있습니다.