[도구정리] 위상정렬(Topological Sort)

🤔 A -> B 관계가 성립하는 DAG에서 어떻게 정렬을 할 수 있을까?

DAG부터 알아보자.

DAG란 Directed Acyclic Graph의 약자로 방향성이 있으며 사이클이 없는 그래프를 말한다.

 

무슨 말일까?

출처 : https://steemit.com/dag/@cryptodreamers/dag-dag-directed-acyclic-graph

위의 그림을 보면 더욱 명확하게 이해가 될 것이다. A -> C, A -> B의 간선이 존재하지만 C -> A, B -> A로 갈 수 있는 방법이 없기 때문에 사이클이 존재하지는 않는다.

 

우리는 이러한 관계에서 어떠한 규칙에 따라 이를 정렬하고 싶은 경우를 알아볼 것이다.

---

📖 위상정렬이란?

 

사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

 

여기서 하나의 용어를 알아야 한다. 바로 진입 차수(Indegree)이다.

예를 들면 2의 경우 자신에게 들어오는 엣지가 1개이므로 1이 되고, 5의 경우 3이 된다.

 

1️⃣ 진입차수가 0인 모든 노드를 큐에 넣는다

큐를 하나 만들어 진입차수가 0인 모든 노드를 큐에 넣는다.

노드	1	2	3	4	5	6	7
진입차수	0	1	1	1	3	2	1

 

Queue에 노드 1이 들어간다.

Queue : 1

---

2️⃣ 큐가 빌 때까지 아래의 과정을 반복한다

3️⃣ 큐에서 원소를 꺼내 해당 노드에서 나가는 간선 그래프를 제거한다

위의 빨간색 간선 두개가 사라진다.

노드	1	2	3	4	5	6	7
진입차수	0	0	0	1	3	2	1

 

4️⃣ 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다

 

노드 2 3이 0이 되었으므로 큐에 넣어준다.

Queue : 2 3

 

이를 큐가 빌때까지 반복한다.

---

💡문제 적용

 

여기까지만 봤을 때는 그래서 언제 어떻게 써야 되지?라는 의문이 들 수 있다.

그렇기에 문제를 통해 보다 자세하게 이해해보자.

https://www.acmicpc.net/problem/2252

 

문제를 읽어보며 위상정렬과 매칭해 보자.

1->3, 2->3 과 같이 방향성 있는 그래프가 제시된다.

이때, 키라는 특수적인 조건상 사이클이 존재할 수 없다.

-> 즉! DAG이고, 이를 정렬하는 문제이다. -> 위상정렬이다.

💻 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] indegree = new int[N + 1];
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            edges.add(new ArrayList<>());
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            indegree[B]++;
            edges.get(A).add(B);
        }

        List<Integer> answer = new ArrayList<>();

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

        while(!queue.isEmpty()){
            int cur = queue.poll();
            answer.add(cur);
            for(int next : edges.get(cur)){
                indegree[next]--;
                if(indegree[next] == 0){
                    queue.add(next);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i : answer){
            sb.append(i).append(" ");
        }

        System.out.println(sb);
    }

}

 

코드를 간단하게 분석해 보자.

일단 List<List<>> 자료구조를 이용하여 각 노드마다 간선의 정보를 저장한다.

이 과정에서 진입차수 역시 확인해 둔다.

 

1. 진입차수가 0인 노드를 큐에 넣는다.

2. 큐가 빌 때까지 반복한다.

3. 큐에서 꺼낸 노드의 간선을 제거한다.

4. 진입차수가 0이 된 노드가 있다면 큐에 추가한다.

 

이 과정 속에서 큐에서 나온 것을 answer 리스트에 추가해 준 뒤에 정답을 출력하면 되는 것이다!