위상정렬 Topology Sort, 백준 1766 문제집(Java)

위상 정렬(Topology Sort)

정렬 알고리즘의 일종으로, 순서가 있는 작업을 차례대로 수행해야 하는 경우 사용할 수 있는 알고리즘이다.

방향 그래프로의 모든 그래프를 방향을 거스르지 않도록 순서대로 나열하는 것이다.

2번을 풀기 전에 1번

3번을 풀기 전에 2번 ,4번

4번을 풀기전에 5번을 푸는 것이  좋다고 하는 상황이 있다면

우리는 다음과 같은 방법들로 문제를 푸는 것이 좋다면 

1->2->5->4->3

1->5->2->4->3 

과 같이 다양한 경우가 만들어 질수 있다(이 외에도 가능하다)

이렇게 정렬하는것이 위상정렬이다.

 

추가로 위에 상황에서  쉬운 문제를 먼저 푸는 것을 우선으로 한다고 하면

1->2->5->4->3 같은 순서로 답을 낼 수 있을것이다.

[(숫자: 난이도, 1번이 제일 쉬운문제)]

---

 

위상 정렬을 계산하기 위해서는 자신에게 들어오는 방향 간선의 수를 저장하는 indegree []와 해당문제를 푼 후 다음에 풀 수 있는 문제를 나타내는 이후 값을 저장하는 graph(List)를 활용한다.

 

위상 정렬 알고리즘은 다음의 순서를 따라서 계산한다.

1) indegree가 0인 노드를 큐에 넣는다 ( 진입 차수가 0인 노드를 큐에 넣는다, 이경우는 그전에 풀어야 하는 문제가 없는 경우이다, 만약 진입 차수가 모두 1이상인 경우는 이미 사이클이 완성된 상황이므로 위상정렬이 불가능 하다.)

2 - 1) 큐에서 원소를 꺼내서 해당 노드를 꺼내서 ans에 넣고, 해당 노드가 진입하는 다음 노드들의 indegree값을 -1 해준다(해당 노드를 해결하였기 때문에 집입 차수가 줄어든다)

2- 2) 만약 지우고 난 후에 indegree의 값이 0이 된다면 해당 노드는 실행 가능하게 된 것으로 큐에 넣는다 

3) 2과정을 큐가 빌 때까지 반복한다. 

 

테이블은 index와 indegree의 값이다.

편의로 노드는 1부터 시작하였다.

아래의 경우는 큐가 기본인 경우이고 만약 우선순위 큐에 정렬한다면 1,2,5,4,3과 같은 순서로 정렬된다.

 

 

 

---

백준 1766 문제집 

1766번: 문제집

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

public class Main {
    private static StringBuildersb= new StringBuilder();

    private static void topologicalSort(ArrayList<ArrayList<Integer>> graph, int[] indegree,int v){
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0;i<v;i++) {
        	if(indegree[i]==0) 
            	queue.add(i);
        }


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

            for(int next : graph.get(now)){
                indegree[next]--;
                if(indegree[next]==0) queue.add(next);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int rule = Integer.parseInt(st.nextToken());
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

        int indegree[] = new int[v];
        //Init
        for(int i=0;i<v;i++) graph.add(new ArrayList<Integer>());

        for(int i=0;i<rule;i++){
            st = new StringTokenizer(br.readLine());
            int s= Integer.parseInt(st.nextToken())-1;
            int e = Integer.parseInt(st.nextToken())-1;
            graph.get(s).add(e);
            indegree[e]++;
        }
        topologicalSort(graph,indegree,v);
        System.out.println(sb);
    }
}

 

input	output
5 4 1 2 2 3 4 3 5 4	1 2 5 4 3

출력됨을 확인할 수 있다.