백준 JAVA 2252번 줄세우기

문제 링크: https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

 

 

키를 정렬하는데 있어서 약간의 순서를 줬다. 즉 어떤 학생 앞에는 정해진 학생이 앞에 있어야 하는 것이다. 

arr배열에 조건의 수를 적어주고 list[해당 학생].add(앞에 서야하는 학생)식으로 선언해준다. arr[학생]==0 일 경우에 StringBuilder에 추가해주며 해당 학생 앞에 서야하는 학생의 arr을 낮춰준다. 이때 낮춰준 학생의 arr==0을 만족할 경우 queue에 넣어준다.

 

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

public class Main {

    static int n;
    static int m;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();
    static List<Integer>[] list;
    static Queue<Integer> queue = new LinkedList<>();

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        list = new ArrayList[n + 1];
        arr = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            String[] s1 = br.readLine().split(" ");
            int before = Integer.parseInt(s1[0]);
            int post = Integer.parseInt(s1[1]);
            arr[post]++; // 조건 수 증가. 
            list[before].add(post); // 해당 학생의 앞에 서야하는 학생들을 넣어준다. 
        }

        for (int i = 1; i <= n; i++) {
            if(arr[i]==0){
                queue.add(i); // 조건이 없는 학생들을 넣어준다. 
            }
        }

        while (!queue.isEmpty()){
            Integer poll = queue.poll();
            sb.append(poll+" "); // 조건을 만족하는 학생들을 넣어준다. 
            for(Integer a: list[poll]){
                arr[a]--; // 해당 학생을 앞에 세워야 하는 조건을 가진 학생들의 값을 낮춰준다.
                if(arr[a]==0){
                    queue.add(a);
                }
            }
        }
        System.out.println(sb.toString());
    }
}