위상 정렬(topology sort)

위상 정렬이란?

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 = in-degree(진입차수)를 이용한 정렬

 

- 기능 : 노드 간의 순서를 결정

- 특징 : 사이클이 없어야 함

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

 

* V : 노드 수, E : 에지 수

 

 

위상 정렬 원리

1. 진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다.

(아래 그래프는 사이클이 없는 상태임)

 

진입 차수 배열 D를 다음과 같이 업데이트 한다.

ex) 4로 들어오는 경로가 두가지 이므로 D[4] = 2

 

 

2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 배열에 저장한다.

그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.

 

 

진입 차수가 0인 1을 선택하여 2, 3의 진입 차수를 1씩 빼 D[2], D[3]이 0이 된다.

그 다음 진입 차수가 0인 노드 2를 선택해 이를 반복한다.

...

모든 노드가 정렬될 때까지 반복한다.

 

 

 

이때, 만약 노드 1 선택 후 노드 2가 아닌 노드 3을 선택했더라면 3이 우선 위상 저렬 배열에 들어갈 것이다.

-> 위상 정렬은 늘 같은 정렬 결과를 보장하지 않는다!

 

 

3. 위상 정렬 배열 결과는 아래와 같다.

---

백준 온라인저지 2252번

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P2252_줄세우기 {
    // 답이 여러가지일 경우 아무거나 출력하라 -> 위상 정렬 힌트

    /* 위상 정렬 수행 과정
     * 1. 진입차수가 0인 노드를 큐에 저장
     * 2. 큐에서 데이터를 poll해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소시킨다.
     * 3. 감소했을 때 진입차수가 0이 되는 노드를 큐에 offer한다.
     * 4. 큐가 빌 때까지 1 ~ 3을 반복한다.
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        // 인접리스트 생성 및 초기화
        ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
        for(int i=0; i<=N; i++) {
            arr.add(new ArrayList<>());
        }

        // 진입 차수 배열 초기화
        int indegree[] = new int[N+1];

        for(int i=0; i<M; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            arr.get(s).add(e);
            indegree[e]++; // 진입차수 배열 데이터 저장!
        }

        // 위상 정렬 수행
        Queue<Integer> queue = new LinkedList<>();

        for(int i=1; i<=N; i++) {
            // 진입 차수가 0이라면 offer
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }

        while(!queue.isEmpty()) {
            int now = queue.poll();
            System.out.print(now + " ");

            for(int next : arr.get(now)) {
                indegree[next]--;

                if(indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
    }
}

---

백준 온라인저지 1516번

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P1516_게임개발하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 건물 종류 수

        ArrayList<ArrayList<Integer>> arr = new ArrayList<>(); // 인접리스트
        for(int i=0; i<=N; i++) {
            arr.add(new ArrayList<>());
        }
        int[] indegree = new int[N+1]; // 진입차수 배열
        int[] selfBuild = new int[N+1]; // 정답 배열 : 각 건물을 짓는데 걸리는 시간

        for(int i=1; i<=N; i++) {
            int time = sc.nextInt(); // 건물을 짓는데 걸리는 시간
            selfBuild[i] += time;

            while(true) {
                int n = sc.nextInt();
                if(n == -1) {
                    break;
                }
                arr.get(n).add(i);
                indegree[i]++;
            }
        }

        // 위상 정렬 수행
        Queue<Integer> queue = new LinkedList<>();
        for(int i=1; i<=N; i++) {
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] result = new int[N+1];
        while(!queue.isEmpty()) {
            int now = queue.poll();

            for(int next : arr.get(now)) {
                indegree[next]--;

                result[next] = Math.max(result[next], selfBuild[now] + result[now]);

                if(indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        for(int i=1; i<=N; i++) {
            System.out.println(result[i] + selfBuild[i]);
        }
    }
}