[정리] 위상정렬

위상정렬

• 정렬알고리즘이며, 순서가 정해져 있는 일련의 작업을 차례로 수행할 때 사용된다.
• 또한, 사이클이 없는 방향 그랲의 모든 노드를 방향성에 어긋나지 않게 나열한다.

문제와 코드를 통해서 알아보겠다

• 백준 (2252번) 줄 세우기

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

풀이

package TopologySort;

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

public class LineSort {
    static int[] cost;
    static Map<Integer, List<Integer>>map = new HashMap<>();

    static void topologySort(){

        Deque<Integer> q = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        for(int i = 0;i<cost.length;i++){
            if(cost[i] == 0)
                q.offer(i+1);
        }
//      위상정렬 알고리즘
        while(!q.isEmpty()){
            int val = q.poll();
            sb.append(val+" ");
            for(int i : map.get(val)) {
                cost[i-1]--;
                if (cost[i - 1] == 0)
                    q.offer(i);
            }
        }
        sb.setLength(sb.length()-1);
        System.out.println(sb.toString());
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        for(int i = 1 ; i<=n;i++)
            map.put(i,new ArrayList<>());
        cost = new int[n];
        for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int f = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            map.get(f).add(s);
            cost[s-1]++;
        }
        topologySort();
    }