[백준] 1766번 : 문제집

문제

www.acmicpc.net/problem/1766

1766번: 문제집

문제해결방법

이 문제는 위상정렬 문제였는데 이 전에 풀었던 문제와 다른 점은 가능하면 쉬운 문제부터 풀어야 한다는 점이였다.

이 부분을 해결하기 위해 Priority Queue를 사용해서 문제집들을 정렬해서 출력해주었다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main1766_문제집 {
 
    public static int[] need;
    public static List<Integer>[] edge;
    public static PriorityQueue<Integer> pq;
        
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        edge = new List[n+1];
        need = new int[n+1];
        pq = new PriorityQueue<Integer>();
        for(int i=1; i<=n; i++) edge[i] = new ArrayList<Integer>();
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            edge[A].add(B);
            need[B]+=1;
        }
        
        for(int i=1; i<=n; i++) {
            if(need[i]==0) pq.add(i);
        }
        while(!pq.isEmpty()) {
            int cur = pq.poll();
            bw.write(cur+" ");
            for(int i=0; i<edge[cur].size(); i++) {
                int next = edge[cur].get(i);
                need[next]--;
                if(need[next]==0) pq.add(next);
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.