[BOJ] 14567. 선수과목 (Prerequisite) (🥇, 위상 정렬)

🔗

풀이

과목들은 위의 그림과 같은 관계를 가지고 있다. 해당 그림에서 선수 과목은 파란선으로 표시된다. 선수 과목이 없는 경우 1학기에 바로 들을 수 있고 해당하는 과목들은 1, 4, 6이 된다.

1학기에 들은 과목을 제외하면 남은 과목은 위와 같다. 5를 듣기 위해서는 2를 먼저 들어야 한다. 2학기에 들을 수 있는 과목은 2, 3이 된다.

2, 3을 수강하면 남은 과목은 5가 된다. 3학기에는 5를 수강하면 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] terms = new int[N+1];
        int[] prerequisite = new int[N+1];
        Map<Integer, List<Integer>> subjects = new HashMap<>();
        for (int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            
            if (!subjects.containsKey(A)) {
                subjects.put(A, new ArrayList<>());
            }
            subjects.get(A).add(B);
            prerequisite[B]++;
        }

        Queue<int[]> queue = new LinkedList<>();
        
        for (int i = 1; i < N+1; i++) {
            if (prerequisite[i] == 0) {
                queue.add(new int[]{i, 0});
            }
        }

        while (!queue.isEmpty()) {
            int[] subInfo = queue.poll();
            
            int subNum = subInfo[0];
            int term = ++subInfo[1];
            terms[subNum] = term;
            if (subjects.getOrDefault(subNum, null) != null) {
                for (int nextSubNum : subjects.get(subNum)) {
                    prerequisite[nextSubNum]--;
                    if (prerequisite[nextSubNum] == 0) {
                        queue.add(new int[]{nextSubNum, term});
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N+1; i++) {
            sb.append(terms[i] + " ");
        }

        System.out.println(sb);
    }
}