줄세우기 - 위상정렬, Java

위상 정렬이란 '순서가 정해져있는 작업' 을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘입니다. 

 

1. 집입차수가 0인 정점을 큐에 삽입합니다. 

2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거합니다. 

3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입합니다. 

4. 큐가 빌 때까지 2번 ~ 3번 과정을 반복합니다. 모든 원소를 방문하기 준에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과입니다. 

 

m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

<문제>

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

package Sort;

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

public class LineUp {

    static int n,m;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());


        HashMap<Integer, ArrayList<Integer>> mp = new HashMap<Integer, ArrayList<Integer>>();
        Queue<Integer> q  = new LinkedList<>();

        int[] count = new int[n + 1];

        for(int i=1; i<=n; i++){
            mp.put(i,new ArrayList<Integer>());
        }

        for (int i = 0; i < m; i++) {

            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());


            mp.get(a).add(b);

            count[b]++;
        }

        for (int i = 1; i <= n; i++) {
            if(count[i]==0){
                q.add(i);
            }
        }

   while(!q.isEmpty()){

       Integer num = q.poll(); //nullpoiner exception 없음
       System.out.println(num + " ");


           for (int j : mp.get(num)) {
               count[j]--;
              if( count[j] == 0){
                  q.add(j);
              }
           }
   }
    }
}