[백준] 줄 세우기(2252)

• 위상정렬 문제이다.
• 위상정렬은 진입차수와 큐로 해결할 수 있다.
  
• 진입 차수가 0인 1을 선택한다.
  
• 선택하지 않은 정점중에서 진입차수가 0인 3을 선택한다. 다음 정정부터는 이와 같은 방법으로 진행한다.
  
  
  
• 이렇게 순서대로 진행하면 1-3-4-2-5 순으로 정렬할 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        int in[] = new int[N+1];
        // 초기화
        for(int i=0;i<=N;i++) { 
            list.add(new ArrayList<>());
        }
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int f = Integer.parseInt(st.nextToken());    // 앞 학생
            int l = Integer.parseInt(st.nextToken());    // 뒤 학생
            list.get(f).add(l);                          // 자기가 가리키고 있는 정점의 정보를 저장
            in[l]++;                                     // 진입차수를 센다.
        }

        Queue<Integer> q = new LinkedList<Integer>();
        Queue<Integer> result = new LinkedList<Integer>();

        for(int i=1;i<N+1;i++) {
            if(in[i]==0)                                // 진입차수가 0인 정점을 큐에 넣는다.        
                q.offer(i);
        }
        while(!q.isEmpty()) {
            int num = q.poll();
            result.offer(num);                          // 결과값을 넣는다.

            for(Integer item:list.get(num)) {           // 자기가 가리키고 있는 정점들
                in[item]--;                             // 진입차수를 빼준다.
                if(in[item] == 0) {                     // 진입차수가 0이면 큐에 넣는다.
                    q.offer(item);
                }
            }
        }
        while(!result.isEmpty()) {
            bw.write(result.poll()+" ");
        }
        bw.flush();
        bw.close();
    }
}