[백준] 1766 문제집

www.acmicpc.net/problem/1766

1766번: 문제집

2021-01-27

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main1766 {
    public static List<List<Integer>> list;
    public static int N, M, arr[];
    public static PriorityQueue<Integer> q;
    public static StringBuilder sb;
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        list = new ArrayList<>();
        q = new PriorityQueue<>();
        arr = new int[N+1];
        sb = new StringBuilder();
        
        for(int i = 1; i <= N+1; i++) list.add(new ArrayList<>());
        
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            arr[b]++;
        }
        
        for(int i = 1; i <= N; i++) {
            if(arr[i] == 0) q.add(i);
        }
        
        while(!q.isEmpty()) {
            int tmp = q.poll();
            sb.append(tmp + " ");
            
            for(int i = 0; i < list.get(tmp).size(); i++) {
                int num = list.get(tmp).get(i);
                if(--arr[num] == 0) q.add(num);
            }
        }
        
        System.out.println(sb.toString());
    }
}

#문제풀이

 

위상정렬 + 우선순위 큐를 이용한 문제이다.

 

1. List<List<Integer>> 형태로, 먼저 푸는 것이 좋은 문제 번호를 순서대로 넣는다 .

 

2. 1차원 배열 arr는 각각의 문제에 대한 진입 차수를 ++ 해준다.

 

3. 맨 처음 진입 차수가 0인 문제를 priorityqueue에다가 넣어준다. 

 

4. queue에 연결된 문제 들을 하나씩 제거해주면서, 새로운 문제를 queue에 추가한다. queue에 값이 없을 때 까지 돈다.