[BOJ] 1766. 문제집 (🥇, 위상 정렬)

🔗

풀이

위상 정렬 알고리즘 문제인데 먼저 풀어야 하는 문제가 없는 문제들 중에서 가장 쉬운 문제(숫자가 낮은 문제)부터 풀어야 하기 때문에 조건에 해당하는 문제들을 담을 때 큐를 우선순위 큐를 사용했다. 매번 정렬하는 대신 매번 풀어야 하는 문제가 가장 작은 문제부터 나올 수 있도록 했다.

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int A;
        int B;
        List<List<Integer>> workbook = new ArrayList<>();
        int[] priority = new int[N+1];
        for (int i = 0; i <= N; i++) {
            workbook.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            priority[B]++;
            workbook.get(A).add(B);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 1; i <= N; i++) {
            if (priority[i] == 0) {
                pq.add(i);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            int problem = pq.poll();
            
            sb.append(problem + " ");
            for (int nextProblem : workbook.get(problem)) {
                priority[nextProblem]--;
                if (priority[nextProblem] == 0) {
                    pq.add(nextProblem);
                }
            }
        }
        System.out.println(sb);
    }
}