BOJ 1766번 문제집 ( 위상 정렬, 우선순위 큐) JAVA

BOJ 1766번 문제집 ( 위상 정렬, 우선순위 큐) JAVA

---

풀이

위상 정렬을 이용하는 문제이다.

그에 대한 근거는 어떤 것이 먼저 오는지 우선순위를 알려주고, 그에 대한 정렬을 하는 것을 문제에서 요구하고 있다는 것이다.

 

추가로 우선순위 큐를 활용해야 되는데, 그 이유는 문제의 3번 조건인

가능하면 쉬운 문제부터 풀어야 한다.

위의 조건이 있기 때문이다.  나머지 풀이는 아래 소스 코드를 참고하길 바란다.

링크

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

 

소스 코드

---

package boj;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Boj1766 {
    static int n, m;
    static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
    static int[] parentNum;
    static ArrayList<Integer> ans = new ArrayList<>();
    static PriorityQueue<Integer> pq = new PriorityQueue<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i <= n; i++) {
            map.add(new ArrayList<>());
        }
        parentNum = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int a, b;
            a = sc.nextInt();
            b = sc.nextInt();
            map.get(a).add(b);
            parentNum[b]++;
        }


        for (int i = 1; i <= n; i++) {
            if (parentNum[i] == 0) {
                pq.add(i);
            }
        }

        while (!pq.isEmpty()) {
            int cur = pq.poll();
            ans.add(cur);
            for (int next : map.get(cur)) {
                parentNum[next]--;
                if (parentNum[next] == 0)
                    pq.add(next);
            }
        }

        for (int temp : ans) {
            System.out.print(temp + " ");
        }
        System.out.println();


    }
}