백준 1766번 : 문제집 java

이 문제는 위상 정렬과 우선순위 큐를 이용하여 푸는 문제입니다.

먼저 푸는 것이 좋은 문제들이 존재하여 이를 조건에 맞게 정렬해주는 위상 정렬 알고리즘을 사용하고 문제를 풀 때 낮은 번호의 문제를 먼저 푸는 것이 좋기 때문에 우선순위 큐를 이용하여 낮은 번호의 문제를 뽑아내야 합니다.

위의 예제를 살펴보도록 하겠습니다.

위 문제는 위와 같은 구조를 이루고 있습니다.

1번과 2번 문제는 각각 3번, 4번 문제를 먼저 해결해야 하므로 parentNum이 1입니다.

이제 parentNum이 0이라서 먼저 풀어도 상관없는 정점들을 PriorityQueue에 넣어줍니다.

이제 PriorityQueue의 가장 앞에 있는 문제를 풀어주겠습니다.

3번 문제를 풀었으니 이제 1번 문제의 parentNum이 0이 되어 풀 수 있게 됩니다.

따라서 PriorityQueue에 1을 추가해줍니다.

1을 추가하면 PriorityQueue는 최소 힙이므로 4와 나오는 순서가 바뀝니다.

이제 PriorityQueue에서 다음 문제를 풀어줍니다.

그다음 순서인 4번 문제를 풀어주면 2번 문제도 풀 수 있게 되어 PriorityQueue에 들어갑니다.

마지막 문제까지 해결하면 문제를 해결하는 순서가 다음과 같이 됩니다.

이제 이 알고리즘을 이용하여 문제를 해결해보도록 하겠습니다.

---

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

public class Main {
    static int N;
    static int[] parentNum;
    static int[] answer;
    static List<List<Integer>> l = new ArrayList<>();

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

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        parentNum = new int[N+1];
        answer = new int[N+1];
        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

        while(M-->0){
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            l.get(A).add(B);
            parentNum[B]++;
        }

        topologicalSort();

        for(int i = 1; i<=N; i++)
            System.out.print(answer[i]+" ");
        System.out.println();
    }

    static void topologicalSort(){
        Queue<Integer> q = new PriorityQueue<>();
        int idx = 1;

        for(int i = 1; i<=N; i++)
            if(parentNum[i] == 0)
                q.offer(i);

        while(!q.isEmpty()){
            int num = q.poll();

            answer[idx++] = num;

            for(int i = 0; i<l.get(num).size(); i++){
                int nextNum = l.get(num).get(i);

                parentNum[nextNum]--;

                if(parentNum[nextNum] == 0)
                    q.offer(nextNum);
            }
        }
    }
}