백준 - 문제집

문제 설명

가장 쉬운 문제부터 풀수 있는 과정을 출력하는 문제이다.

단, 문제마다 먼저 풀어야 하는 문제를 모두 풀어야 다음 문제를 풀어야 한다.

주의사항

문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.

이점을 생각하면 낮은 번호의 문제부터 풀어야 하므로 일반 큐가 아닌 우선순위 큐를 이용해야 한다.

풀이

public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(reader.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] indegrees = new int[n + 1];

		List<Integer> adj[] = new List[n + 1];

		for (int i = 1; i <= n; i++) {
			adj[i] = new ArrayList<>();
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(reader.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			adj[from].add(to);
			indegrees[to]++;
		}

		PriorityQueue<Integer> q = new PriorityQueue<>(); // 일반 큐로 하면 3,4,1,2 | (3,4) -> 진입차수 0인거 넣고
		for (int i = 1; i <= n; i++) {
			if (indegrees[i] == 0)
				q.offer(i);
		}

		StringBuilder answer = new StringBuilder();
		while (!q.isEmpty()) {
			Integer cur = q.poll();
			answer.append(cur+" ");
			for (Integer next : adj[cur]) {
				indegrees[next]--;

				if(indegrees[next]==0){
					q.offer(next);
				}
			}
		}

		System.out.println(answer);
	}