백준 1766 문제집 Java [위상정렬, 우선순위 큐]

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

1766번: 문제집

 

 

위상정렬과 우선순위큐를 사용해서 풀이하면 된다

입력 값에 맞게 가중치를 추가해주고

1부터 N까지 가중치가 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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int[] degree = new int[N + 1];
        ArrayList<Integer>[] next = new ArrayList[N + 1];
        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);
    }
}