[BOJ] 2252. 줄 세우기

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

접근 방법

간단한 위상 정렬의 문제이다.

Need Know

1. 위상 정렬

전체 코드 ( Java )

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int N;
    static int M;
    static int[] preceding_num;
    static ArrayList<Integer>[] preceding_rule;
    static Queue<Integer> queue;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException{
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        preceding_num = new int[N+1];
        preceding_rule = new ArrayList[N+1];
        queue = new PriorityQueue<>();
        for(int i=1; i<N+1; i++){
            preceding_rule[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            preceding_rule[a].add(b);
            preceding_num[b] ++;
        }

    }
    static void solve() throws IOException {
        for(int i=1; i<N+1; i++){
            if(preceding_num[i] == 0){
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            int vertex = queue.poll();
            bw.write(vertex + " ");
            for(int i=0; i<preceding_rule[vertex].size(); i++){
                int nv = preceding_rule[vertex].get(i);
                preceding_num[nv] --;
                if(preceding_num[nv] == 0){
                    queue.add(nv);
                }
            }
        }
    }
}