[BOJ] 1766. 문제집

문제 원본 : https://www.acmicpc.net/problem/1766

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder builder = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        ArrayList<Integer>[] adj = new ArrayList[n + 1];
        int[] c = new int[n + 1];

        for (int i = 1; i <= n; ++i) {
            adj[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());

            adj[a].add(b);
            ++c[b];
        }

        for (int i = 1; i <= n; ++i) {
            Collections.sort(adj[i]);
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 1; i <= n; ++i) {
            if (c[i] == 0) {
                priorityQueue.add(i);
            }
        }

        while (!priorityQueue.isEmpty()) {
            int curr = priorityQueue.poll();
            builder.append(curr).append(" ");

            for (int next : adj[curr]) {
                --c[next];

                if (c[next] == 0) {
                    priorityQueue.add(next);
                }
            }
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }
}

• 위상 정렬 문제
• 일반 위상 정렬 문제에서 큐를 우선순위 큐로만 바꿔주면 해결된다.