BOJ_2252_줄 세우기_java

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

2252번: 줄 세우기

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

public class BOJ_2252_줄세우기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] inDegree = new int[n+1]; // 각 노드의 진입 차수 (1번 노드부터 시작)
        List<Integer>[] edges = new List[n+1]; // 간선 정보
        for (int i = 1; i<=n; i++){ // 간선 정보 초기화
            edges[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());
            edges[a].add(b); // 간선 정보 입력 a -> b
            inDegree[b]++; // 진입 차수
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i<=n; i++){ // 진입 차수가 0인 것 찾기
            if (inDegree[i] == 0){
                queue.offer(i);
                inDegree[i] = -1; // 해당 노드 완료 표시
                while (!queue.isEmpty()){
                    int node = queue.poll();
                    sb.append(node).append(" ");
                    for (int next : edges[node]){ // 다음 노드 검색
                        inDegree[next]--;
                        if (inDegree[next] == 0){ // 진입 차수가 0인경우 큐에 입력
                            queue.offer(next);
                            inDegree[next] = -1; // 해당 노드 완료 표시
                        }
                    }
                }
            }
        }

        System.out.println(sb.toString());

    }

}