<Algorithm> 86. 1766번 문제집

1. 1766번 문제집

• 우선순위 큐를 이용한 위상정렬 문제

• 가중치와 정점으로 정렬을 하려고 했는데 생각해보니 정점으로만 위상정렬을 하면되는 간단한 문제였다.

• 선수과목이 있는데 가나다 순으로 과목을 이수하라는 의미와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static ArrayList<Integer> alist[];
    public static int prio[];
    public static StringBuilder sb = new StringBuilder("");
            
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken())+1;
        int M = Integer.parseInt(st.nextToken());
        alist = new ArrayList[N];
        prio = new int[N];
        visited = new boolean[N];
        for(int i = 0; i < N ; i++) {
            alist[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());
            alist[a].add(b);
            prio[b]++;
        }
        
        bfs(N);
        System.out.println(sb.toString());
            
    }
    
    public static boolean[] visited;
    public static void bfs(int N) {
     PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                // TODO Auto-generated method stub
                return o1.vertax - o2.vertax;
            }
        });
        
        for(int i = 1 ; i < N ; i++) {
            if(prio[i] == 0) {
                pq.add(new Node(i));
            }
        }
        
        while(!pq.isEmpty()) {
            int vertax = pq.remove().vertax;
            sb.append(vertax + " ");
            
            for(Integer in: alist[vertax]) {
                prio[in]--;
                if(prio[in] == 0) {
                    pq.add(new Node(in));
                }
            }
        }
        
    }
    
}
class Node {
    int vertax;
    public Node(int v) {
        super();
        this.vertax = v;
    }
}

참고 & 출처