백준 1766번 문제집 (JAVA)

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

1766번: 문제집

 

저는 우선순위 큐를 이용해 문제를 해결하였습니다.

각각의 일이 이전에 몇개의 작업이 필요한지를 세고 이 값이 0인 값만 먼저 우선순위 큐에 넣었습니다.

우선순위 큐에 빼면서 해당 작업이 필요했던 작업의 필요한 작업 개수를 줄이고 해당 값이 0 이라면 우선순위 큐에 넣어서 문제를 해결하였습니다.

 

package BOJ.greedy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1766 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int[] cnt = new int[n+1];
        List<Integer>[] nextWork = new List[n+1];
        for(int i = 0 ; i <= n ; i++){
            nextWork[i] = new LinkedList<>();
        }
        for(int i = 0 ; i < m ; i++){
            st = new StringTokenizer(br.readLine());
            int prevWork = stoi.apply(st.nextToken());
            int work = stoi.apply(st.nextToken());
            cnt[work]++;
            nextWork[prevWork].add(work);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 1 ; i <= n ; i++){
            if(cnt[i] == 0){
                pq.offer(i);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            int now = pq.poll();
            sb.append(now+" ");
            for(int next : nextWork[now]){
                if(--cnt[next] == 0) {
                    pq.offer(next);
                }
            }
        }
        sb.setLength(sb.length()-1);
        System.out.println(sb.toString());
    }
}