문제 설명

문제 분석

슈도코드

구현

public class 줄세우기_2252 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(); // 학생의 수
        int M = scan.nextInt(); // 키를 비교한 횟수
        int indegree[] = new int[N + 1]; // 진입 차수 배열

        // 학생 수만큼 인접 리스트 초기화 
        ArrayList<ArrayList<Integer>> student = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            student.add(new ArrayList<>());
        }
        
        // 그래프, 진입 차수 초기화
        for (int i = 0; i < M; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            student.get(s).add(e); // 그래프 정의
            indegree[e]++; // 진입 차수 정의
        }

        // 위상정렬 실행
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if(indegree[i] == 0) {
                q.add(i);
            }
        }

        while (!q.isEmpty()) {
            int curStudent = q.poll();
            System.out.print(curStudent + " ");
            for (int nextNode : student.get(curStudent)) {
                indegree[nextNode]--;
                if(indegree[nextNode] == 0) {
                    q.add(nextNode);
                }
            }
        }
    }
}