문제집 [백준 1766][골드2][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

1766번: 문제집

백준 2252 줄세우기 와 같은 위상정렬 문제.

다른점이 있다면 안의 요소들을 우선순위 큐를 이용하여 정렬해 주어야 한다.

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

public class 문제집 {
	static int N; // 그래프 정점의 수
    static int M; // 간선의 수
    static ArrayList<ArrayList<Integer>> graph;
    static int[] Link;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        Link = new int[N + 1]; // 간선의 수에 대한 배열
        
        //인접리스트
        graph = new ArrayList<>();	

        for (int i = 0; i < N+1; i++) {
        	graph.add(new ArrayList<Integer>());
		}
        
        for (int i = 0; i < M; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			
			graph.get(A).add(B);
			Link[B]++;
		}
        Sort();
	}
	public static void Sort() {
		PriorityQueue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return Integer.compare(o1, o2);
			}
		});
		
		for (int i = 1; i < N+1; i++) {
			if(Link[i] == 0) {
				q.add(i);
			}
		}
		
		while(!q.isEmpty()) {
			int node = q.poll();
			System.out.print(node + " ");
			
			for(int nextNode : graph.get(node)) {
				Link[nextNode]--;
				
				if(Link[nextNode] == 0) {
					q.add(nextNode);
				}
			}
		}
	}

}