위상 정렬 알고리즘

위상 정렬 알고리즘

위상 정렬(Topology Sort)은 순서가 있는 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다. 

위상 정렬을 하기 위해서는 사이클이 없는 방향 그래프 DAG(Directed Acyclic Graph)이여야 한다.

 

위상정렬은 큐와 각 노드의 진입차수(Indegree)를 이용하여 구현할 수 있다.

1. 각 Node 별로 Indegree를 구해준다.

2. Indegree가 0인 Node를 Queue에 넣어준다.

3. Queue에서 Node를 가져와 해당 Node에서 방문 가능한 Node의 Indegree를 감소시킨다.

4. 감소된 Node의 Indegree가 0 이라면 Queue에 넣어준다.

5. Queue가 빌때까지 3,4 작업을 반복한다. 

위와같은 순서로 동작한다면 Queue에서 방문한 순서대로 위상정렬이 된다.

 

예시를 통해 살펴보자.

 

[Step 1] 아래와같이 DAG가 있다. 각 노드별로 Indegree를 구해준 후, Indegree가 0인 Node들을 큐에 넣어준다.

[Step 2] 큐에서 값을 가져와 해당 node를 방문하고 해당 node에서 가리키는 곳의 Indegree를 감소시킨다. 만약 이 작업으로 Indegree가 0이 된 node가 있다면 다시 큐에 넣어준다. 

[Step 3] 2번 Node를 큐에서 가져와 방문하고 방문 가능한 곳의 Indegree를 감소시킨다. Node 4의 Indegree 가 0이 되었으니 큐에 새로 넣어준다.

[Step 4] 큐에서 4번 Node를 가져온후 방문 가능한 곳의 Indegree를 줄여준다. 5번 Node의 Indegree가 0이 되었으니 새로 큐에 넣어준다. 

[Step 5] 큐에서 5번 Node를 가져온후 방문 가능한 곳의 Indegree를 줄여준다. 3번 Node의 Indegree가 0이 되었으니 새로 큐에 넣어준다. 

[Step 6] 큐에서 가져온 Node 3번에서는 더이상 방문 가능한 곳이 없다. 큐가 비었으니 종료된다. 따라서 방문 순서는 

1 - 2 - 4 - 5 - 3 이 된다.

결과로 나온 방문 순서는 1 - 2 - 4 - 5 - 3 이지만 별다른 조건이 없기에 2 - 1 - 4 - 5 - 3 역시 가능한 결과이다. 

 

예시 문제

위상 정렬을 이용하여 백준 1766번 문제를 풀어보자.

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

1766번: 문제집

풀이방법

위상정렬 개념을 안다면 간단하게 풀 수 있다. 좀 더 생각해야 할 점은 풀어야 할 문제의 우선순위가 있다는 것이다. 이 경우 위의 위상정렬에서 사용되는 큐를 우선순위 큐를 이용하면 풀수 있는 문제들중 우선순위를 정하여 풀 수 있다. 

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class P1766 {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] count = new int[N+1];
        HashMap<Integer,ArrayList<Integer>> graph = new HashMap<>();

        for(int i =0; i< M; i++){
            st = new StringTokenizer(br.readLine());
            int prev = Integer.parseInt(st.nextToken());
            int post = Integer.parseInt(st.nextToken());
            count[post] += 1;
            if(graph.get(prev) == null) graph.put(prev, new ArrayList<Integer>());
            graph.get(prev).add(post);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i =1; i<count.length; i++){
            if(count[i] == 0){
                pq.add(i);
            }
        }
        ArrayList<String> answer = new ArrayList<>();
        while(pq.size() > 0){
            int now = pq.poll();
            answer.add(""+now);
            ArrayList<Integer> nowArr = graph.get(now);
            if(nowArr != null){
                for (int i : nowArr) {
                    count[i]--;
                    if(count[i] == 0) pq.add(i);
                }
            }
        }
        System.out.println(String.join(" ",answer));
    }
}