백준 2252 줄 세우기 Java [위상정렬]

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

2252번: 줄 세우기

 

입력을 받고 B는 가중치를 주면서 A의 다음에 나올 수 있는 배열에 추가한다

학생들 중에서 가중치가 0인 인덱스를 큐에 넣고

큐에서 하나씩 빼면서  다음에 나올 수 있는 배열 반복문으로 돌면서

가중치 빼주고 가중치 0인 인덱스를 큐에 넣는 것을 반복한다

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] degree = new int[N + 1];
        ArrayList<Integer>[] next = new ArrayList[N + 1];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) next[i] = new ArrayList<>();
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            degree[B]++;
            next[A].add(B);
        }
        for (int i = 1; i <= N; i++) {
            if (degree[i] == 0) queue.add(i);
        }
        while (!queue.isEmpty()) {
            int now = queue.poll();
            sb.append(now).append(" ");
            for (int n : next[now]) {
                degree[n]--;
                if (degree[n] == 0) queue.add(n);
            }
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }
}