아이디어

• 위상정렬 알고리즘을 사용한다. 자세한 설명은 여기 참고
  • 단, 진입차수가 0이라도 그 중에서 번호가 작은 것을 골라야 하므로 일반 큐 대신 우선순위 큐를 사용한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, M, A, B;
	static List<List<Integer>> graph = new ArrayList<>();
	static int[] indeg;
	static PriorityQueue<Integer> pq = new PriorityQueue<>();
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		
		graph.add(null);
		for (int i=0; i<=N; i++) {
			graph.add(new ArrayList<>());
		}
		indeg = new int[N+1];
		
		for (int i=0; i<M; i++) {
			tk = new StringTokenizer(rd.readLine());
			A = Integer.parseInt(tk.nextToken());
			B = Integer.parseInt(tk.nextToken());
			graph.get(A).add(B);
			indeg[B]++;
		}
		
		// topological sort
		for (int i=1; i<=N; i++) {
			if (indeg[i] == 0) pq.offer(i);
		}
		
		while (!pq.isEmpty()) {
			int x = pq.poll();
			
			sb.append(x).append(' ');
			
			for (int n: graph.get(x)) {
				if (--indeg[n] == 0) {
					pq.offer(n);
				}
			}
		}
		
		System.out.println(sb);
	}
}

메모리 및 시간

• 메모리: 44772 KB
• 시간: 516 ms

리뷰

• 1005번보다 더 쉽고 직관적인데 왜 골드2인지 의아한 문제