[알고리즘] 위상 정렬(Topology Sort)

• 이해를 위한 예시

Q. 고등학교를 가기 위해서는 중학교를 졸업해야하고, 중학교를 가기 위해서는 초등학교를 졸업해야 합니다. 그렇다면 초등학교를 입학한 시점을 기준으로 고등학교에 진학하려면 몇년정도의 시간이 소요될까요?
A. 9년이다(초등학교 6년, 중학교 3년)

Q. 스타크래프트에서 테란 종족 건물인 스타포트를 짓기 위해서는 배럭과 팩토리라는 건물을 먼저 지어야합니다. 팩토리를 지으려면, 배럭을 먼저 지어야합니다.
배럭과 팩토리가 100원, 200원이 든다고 했을 때, 스타포트(300원)를 짓기 위해서 드는 비용은 얼마인가?
A. 100 + 200 + 300 -> 600원

이처럼, 무언가 순차적이고 순서가 정해져있는 일련의 작업을 수행할 때 사용할 수 있는 알고리즘이 바로 위상 정렬이다!

[1] 위상정렬의 정의와 조건

• 정의: 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것이다.
  모든 간선(u,v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬된다.
  
  
• 조건: 사이클이 없는 방향 그래프인 경우에만 사용가능하다.
  위에서의 예시를 보면 중학교에서 초등학교로 내려갈 순 없다.
  만약에 롤 티어가 실버1일 때, "골드1까지 총 포인트 얼마를 획득하여 승급할 것인가?"라고 물었을 때 플레이어가 매번 이길 것이라는 보장이 없기 때문에 답은 여러 개가 될 수 있다. 즉, 점수나 티어가 올라갈 수도, 떨어질 수도 있다. 순환이 생길 수 있기 때문에 이러한 경우에는 위상정렬 알고리즘을 사용하여 답을 내는 것이 불가능하다.
  

---

[2] 위상정렬 과정

먼저, 필요한 자료구조를 먼저 정리해보도록 하자.
1) 진입차수( 본인 노드를 기준으로 화살표가 들어오는 방향 갯수)를 저장하는 배열 -> indegree라고 부르기로 약속하자.
2) 본인 노드에서 어떤 노드를 갈 수 있는지에 대한 정보를 관리하는 리스트 -> graph라고 부르기로 약속하자.
3) 순차적으로 노드를 탐색하기 위한 Queue가 필요하다.

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

2) 큐에서 노드를 하나씩 꺼내면서 인접한 노드를 찾아가면서 indegree를 1씩 감소시킨다. 이때, 만약 indegree가 0이 되었다면 큐에 넣는다. 아래에서 b는 a에 의해 indegree가 1이 감소하여 1(2-1)이 되었고, d는 a에 의해 1이 감소하여 0이 되어 큐에 들어간 것을 그림을 통해 확인할 수 있다.

3) 2번과정과 동일하게 큐에서 노드를 꺼내고, 인접한 노드의 indegree를 1 감소시키며 인접한 노드의 indegree가 0이 된 노드만 큐에 넣어준다.

4) b노드를 큐에서 꺼내고, c/g의 indegree를 1 감소시켰고 0이 되어 큐에 넣어준 모습이다.

5) c,g를 큐에서 꺼내어 f의 indegree를 0으로 만들어 f를 큐에 넣고, f를 꺼냈을 때 인접한 노드가 없으므로 탐색을 종료하면 된다.

내용을 정리하면 다음과 같다.

[1] 시작 노드(indegree가 0인 노드)를 큐에 넣는다.
[2] 큐에서 꺼낸 노드의 인접한 노드들의 indegree를 1 감소시킨다. 이때, 감소시킨 뒤에 indegree가 0이 되었다면 큐에 넣어준다.
[3] 2번의 과정을 반복한 끝에, 큐가 비었다면 탐색을 종료한다.

위의 과정을 코드를 보며 이해해보자

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

public class Main {

    public static Map<Character, List<Character>> graph = new HashMap<>();
    public static int N, M;
    public static Map<Character, Integer> indegree; 
    // indegree가 배열이 아니라고 당황할 필요 없다!  
    // 특정 문자(노드의 값)의 indegree를 해쉬맵으로 표현한 것 뿐이다.

    public static void tpSort() {
        Queue<Character> q = new ArrayDeque<>();
        //[1]번 과정으로 시작 노드를 큐에 넣어준다.
        for (char i = 'A'; i < 'A' + N; i++) {
            if (indegree.get(i) == 0) {
                q.offer(i);
            }
        }

		// 탐색의 종료조건 큐가 비어있다면, 더이상 확인할 노드가 없다고 간주
        while (!q.isEmpty()) {
            char now = q.poll();
            if (graph.containsKey(now)) {
                for (char newIndex : graph.get(now)) {
                    indegree.put(newIndex, indegree.get(newIndex) - 1);
                    if (indegree.get(newIndex) == 0) {
                        q.offer(newIndex);
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

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

        indegree = new HashMap<>();

        for (char i = 'A'; i < 'A' + N; i++) {
            graph.put(i, new ArrayList<>());
            indegree.put(i, 0);
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            char A = st.nextToken().charAt(0);
            char B = st.nextToken().charAt(0);
            // 인접한 노드들을 리스트로 초기화
            // indegree값도 초기화
            graph.get(A).add(B);
            indegree.put(B, indegree.get(B) + 1);
        }

        tpSort();
        br.close();
    }
}

이러한 알고리즘을 통해, 글 최상단 예시처럼 어떤 순차적인 행위를 하여 특정 행위를 하기 위해서 드는 비용을 묻는 문제가 보통 많이 나오는 것 같다.
-> 정답을 구하기 위해 변수를 추가하여 적절하게 사용하면 된다.
결국, 위상 정렬 알고리즘의 템플릿 코드에 코드를 조금만 추가하면 된다는 것!

시간복잡도는 O(V+E) V는 정점(글에서 노드라고 말했던)의 개수, E는 간선의 개수이다.

관련 문제

백준 선수과목 14567: https://www.acmicpc.net/problem/14567
백준 게임개발 1516: https://www.acmicpc.net/problem/1516