백준 14567번 : 선수과목 (Prerequisite) java

이 문제는 위상 정렬을 이용하여 주어진 조건에 맞게 각 과목을 이수하려면 몇 학기가 걸리는지를 구하는 문제입니다.

위상 정렬을 이용하는 방법은 아래 링크를 참고하시면 좋을 것 같습니다.

백준 1516번 : 게임 개발 java

---

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

public class Main {
    static int N;
    static List<List<Integer>> l = new ArrayList<>();
    static int[] parentNum;
    static int[] answer;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        parentNum = new int[N+1];
        answer = new int[N+1];
        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

        while(M-->0){
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            l.get(A).add(B);
            parentNum[B]++;
        }

        topologicalSort();

        for(int i = 1; i<=N; i++)
            System.out.print(answer[i]+" ");
        System.out.println();
    }

    static void topologicalSort(){
        Queue<Integer> q = new LinkedList<>();

        for(int i = 1; i<=N; i++)
            if(parentNum[i] == 0){
                q.offer(i);
                answer[i] = 1;
            }

        while(!q.isEmpty()){
            int num = q.poll();

            for(int i : l.get(num)){
                parentNum[i]--;

                if(parentNum[i] == 0){
                    q.offer(i);
                    answer[i] = answer[num] + 1;
                }
            }
        }
    }
}