백준 1766 자바 - 문제집 문제

www.acmicpc.net/problem/1766

1766번: 문제집

 

그래프이론, 위상정렬, 우선순위 큐 개념이 들어있는 문제로 문제 풀이방식은 다음과 같다.

 

1. 입력받은 문제들의 index를 graph로 만들고 

2. 각 문제들의 선행되어야하는 문제의 수 즉 진입차수(inDegree)를 배열로 셋팅한다.

3. 우선순위 큐를 index값이 작은 것이 우선되도록 만들고

4. 진입차수가 0인 문제들을 해당 큐에 넣는다.

5. 큐를 돌면서 해당 문제의 index를 출력하고(문제를 풀었다는 내용)

6. 해당문제를 선행으로 가지고있던 문제들의 진입차수를 -1 해준다.

7. 진입차수를 -1 한 문제들 중 진입차수가 0이 된 문제를 큐에 추가해준다.

 

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

// 문제집 문제 - 1766번
public class Main{

    static int N, M;
    static int[] inDegree;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        inDegree = new int[N+1];
        for(int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for(int i = 0 ; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            inDegree[b] += 1;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                pq.offer(i);
            }
        }

        while (!pq.isEmpty()) {
            int now = pq.poll();
            sb.append(now).append(" ");
            ArrayList<Integer> nodes = graph.get(now);
            for(int node : nodes) {
                inDegree[node] -= 1;

                if(inDegree[node] == 0) {
                    pq.offer(node);
                }
            }
        }
        System.out.println(sb.toString());
    }
}