백준 1766 문제집 - 위상정렬

특정 행동에 대해 선행되어야 하는 행동이 있으면 위상정렬문제이다.

2가지 변수를 기억하자. b를 풀기 위해 먼저 풀어야하는 문제의 수를 저장하는 int[] degree 변수

선행문제를 풀었을때는 후행문제의 degree를 낮춰줘야하므로 후행문제를 저정하는 int[][] adj 변수

놓친점 1

위상정렬에 대해 기억이 희미할때 풀었을때 나는 1부터 변수를 증가시키면서 풀지못한 문제를 큐에 넣고 빼서 idx변수와 비교했었는데 틀렸고 이렇게 풀면 안된다.

"우선순위큐"를 기억하자. 우선순위큐를 통해 먼저 풀어야하는 문제가 idx인지 기존에 저장해둔 후행문제인지 고민하지말고 그냥 큐에 넣자..

코드

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

public class Main {

    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


    public static void main(String[] args) throws IOException {

        String[] inp = br.readLine().split(" ");
        int n = Integer.parseInt(inp[0]);
        int m = Integer.parseInt(inp[1]);

        int[] degree = new int[n + 1];
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i < n + 1; i++) {
            adj.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < m; i++) {
            inp = br.readLine().split(" ");
            int a = Integer.parseInt(inp[0]);
            int b = Integer.parseInt(inp[1]);
            // a를 b보다 먼저 풀어야함
            degree[b]++; // b를 풀기우히ㅐ
            adj.get(a).add(b); // a를 풀면 b를 풀수 있어
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();

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

        while (!pq.isEmpty()){

            Integer cur = pq.poll();
            for (int next : adj.get(cur)){
                degree[next]--;
                if (degree[next]==0){
                    pq.add(next);
                }
            }

            System.out.print(String.valueOf(cur)+" ");
        }


    }
}