[Java] 위상정렬

위상 정렬은 특정 수강과목에서 선수과목이 있을 경우 어떤 순서로 들어야 하는지 순서를 쉽게 찾아낼 수 있는 알고리즘입니다.

이때, 위상 정렬을 위해서는 그래프는 방향이 있어야 하고 사이클이 없는 DAG(Directed Acyclic Graph) 여야만 합니다.

 

위상 정렬 방법(Queue 사용)

1. 진입 차수 즉, 특정 노드로 들어오는 간선의 개수를 알아내기 위해 in 배열의 크기를 정점의 개수만큼 만듭니다.

2. 특정 노드로 들어오는 간선이 있을 때마다 in 배열의 크기를 +1 해줍니다.

ex)

예를 들어, 위 이미지와 같은 DAG가 있다면

진입 차수는

	1	2	3	4
진입 차수	0	1	0	3

와 같이 됩니다.

 

3. 큐를 만들고 진입 차수가 0인 노드를 전부 큐에 삽입합니다.

4. 큐에 아무것도 남지 않을 때까지 반복합니다.

   4-1. 큐에서 노드를 꺼내와 해당 노드에서 나가는 간선을 그래프에서 제거하기 위해 해당 노드에서 연결된 노드의 진입 차수를 감소시킵니다.)

   4-2. 새롭게 진입 차수가 0이 된 노드를 큐에 삽입합니다.

   4-3. 4를 반복합니다.

 

위 과정을 거치면 위상 정렬을 수행할 수 있습니다.

---

SWEA의 1267번 작업순서를 예시로 코드를 포함했습니다.

SW Expert Academy

---

코드

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

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = 10;
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");
            int V = sc.nextInt();
            int E = sc.nextInt();
            int[] indegree = new int[V];
            int[][] adj = new int[V][V];

            for (int i = 0; i < E; ++i) {
                int from = sc.nextInt() - 1;
                int to = sc.nextInt() - 1;

                adj[from][to] = 1;
                indegree[to]++;
            }

            Queue<Integer> queue = new LinkedList<Integer>();
            for (int i = 0; i < V; ++i) {
                if (indegree[i] == 0) {
                    queue.offer(i);
                }
            }

            while (!queue.isEmpty()) {
                int node = queue.poll();
                sb.append(node + 1).append(" ");

                for (int i = 0; i < V; ++i) {
                    if (adj[node][i] == 1) {
                        indegree[i]--;

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

            sb.append("\n");
        }

        System.out.println(sb);
        sc.close();
    }
}