알고리즘104 :: BOJ_1766_문제집

import java.util.*;
public class Main {

	static class Empty implements Comparator<Integer>{
		public int compare(int a, int b) {
			return Integer.compare(a, b);
		}

		@Override
		public int compare(Integer o1, Integer o2) {
			// TODO Auto-generated method stub
			return o1-o2;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		ArrayList<Integer>[] al = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			al[i] = new ArrayList<>();
		}
		int[] indegree = new int[n+1];
		for(int i=0; i<m; i++) {
			int first = sc.nextInt();
			int second = sc.nextInt();
			al[first].add(second);
			++indegree[second];
		}
		PriorityQueue<Integer> pq = new PriorityQueue<>(1, new Empty());
		
		for(int i=1; i<=n; i++) {
			if(indegree[i]==0) {
				pq.add(i);
			}
		}
		
		while(!pq.isEmpty()) {
			int k = pq.poll();
			System.out.print(k+" ");
			for(int y : al[k]) {
				indegree[y]-=1;
				if(indegree[y] == 0) {
					pq.add(y);
				}
			}
		}
	}
}

 

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

주어진 3개의 조건을 만족하기 위해서 위상정렬과 우선순위 큐(민-힙) 을 사용해서 해결해야 하는 문제 였습니다.