[BOJ] 1766. 문제집

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

접근 방법

위상 정렬의 문제이다.

여기서의 문제점은 아무리 차수(Preceding_cnt)가 0이면 그에 따른 순서는

문제의 번호를 따르게 된다.

그렇기 때문에 나는 PriorityQueue를 사용하게 되었다.

Priority를 사용하게 된다면 0인 것을 queue에 넣게 되었을 때 우선순위에 맞게 알맞게 넣어줄 수 있기 때문이다.

Need Know

1. 위상 정렬

전체 코드 ( Java )

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int N;
    static int M;
    static int[] preceding_num;
    static ArrayList<Integer>[] preceding_rule;
    static PriorityQueue<Integer> queue;
    static ArrayList<Integer> ans;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException{
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        preceding_num = new int[N+1];
        preceding_rule = new ArrayList[N+1];
        queue = new PriorityQueue<>();
        ans = new ArrayList<>();
        visit = new boolean[N+1];
        for(int i=1; i<N+1; i++){
            preceding_rule[i] = 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());
            preceding_rule[a].add(b);
            preceding_num[b] ++;
        }

    }
    static void solve() throws IOException {
        for(int i=1; i<N+1; i++){
            if(preceding_num[i] == 0){
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            int vertex = queue.poll();
            visit[vertex] = true;
            ans.add(vertex);
            for(int i=0; i<preceding_rule[vertex].size(); i++){
                int nv = preceding_rule[vertex].get(i);
                preceding_num[nv] --;
                if(preceding_num[nv] == 0 && !visit[nv]){
                    queue.add(nv);
                }
            }
        }
        for(int vertex : ans){
            bw.write(vertex +" ");
        }
    }
}