[JAVA]백준 - 2252번 줄 세우기(골드3)

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] students = new int[N+1];
		
		List<List<Integer>> graph = new ArrayList<>(N+1);
		for(int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		
		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			graph.get(a).add(b);
			students[b]++;
		}
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		for(int i = 1; i <= N; i++) {
			if(students[i]==0) {
				pq.offer(i);
			}
		}
		List<Integer> result = new ArrayList<>();
		
		while(!pq.isEmpty()) {
			int cur = pq.poll();
			result.add(cur);
			
			for(int neighbor : graph.get(cur)) {
				students[neighbor]--;
				if(students[neighbor] == 0) {
					pq.offer(neighbor);
				}
			}
		}
		
		for(int stu:result) {
			System.out.print(stu + " ");
		}
		
		sc.close();
		
		
	}

}

• students[i]: 노드 i 로 들어오는 진입 차수
• graph: 인접 리스트로 간선 정보 저장
• 진입 차수 0인 노드를 우선순위 큐에 삽입
• 우선순위 큐를 이용한 위상 정렬 수행
• 큐에서 작은 숫자부터 꺼내며 진행
• cur 에 연결된 노드들의 진입 차수를 감소
• 새롭게 진입 차수 0이 되면 큐에 삽입
• 위상 정렬 결과 출력