백준 - 문제집(1766) - 위상정렬 - Java

1. 문제

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

2. 풀이

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

전제 조건 중에 1번 2번은 위상정렬에 대한 이야기 이고, 3번은 '가능하면 쉬운 문제' 부터 이다. 쉬운 문제 = 번호가 적은 문제부터. 따라서 기존 위상정렬은 Queue를 사용했다면, 이는 PriorityQueue를 사용하여 적은 숫자가 먼저 poll()되도록 설정하면 되는 것이다.

입력 예시

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다.

3. 전체 코드

import java.util.*;
import java.io.*;

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 d[] = new int[N+1];
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for(int i = 0; i <= N; i++){
            d[i] = 0;
            list.add(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());
            
            list.get(A).add(B);
            d[B]++;
        }
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 1; i <= N; i++){
            if(d[i] == 0){
                pq.add(i);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            int n = pq.poll();
            sb.append(n + " ");
            
            for(Integer i : list.get(n)){
                if(--d[i] == 0){
                    pq.add(i);
                }
            }
        }
        
        System.out.println(sb.toString());
        
    }
}