백준 1766 문제집 (JAVA 자바)

문제 출처 - www.acmicpc.net/problem/1766

1766번: 문제집

 

문제 유형 - 위상 정렬

문제는 단순 위상 정렬인데 이제 문제 조건 중에 쉬운 문제부터 풀어야한다는 조건이 있다. 그러니까 문제에서 주어진 테케 경우에 저 조건이 4 2 3 1라면 4 3 2 1 이렇게 풀 수도 있지만 저 조건 떄문에 3 1 4 2 이렇게 풀어야 한다. 맨 처음에는  위상정렬 + DFS로 풀까 하고 생각했는데 일이 좀 커질 것 같았다. 그래서 그냥 큐가 아니라 크기대로 정렬해주는 우선순위 큐를 사용하는게 속 편하다. 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class BJ1766_문제집 {
	static int indegree[];
	static int N;
	static ArrayList<Integer> list[];
	static int M;
	static PriorityQueue <Integer> q;
	static StringBuilder sb;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		q = new PriorityQueue<>();
		sb = new StringBuilder();
		
		list = new ArrayList[N + 1];
		indegree = new int[N + 1];
		
		for (int i = 1; i < N + 1; i++) {
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			indegree[end]++;
			list[start].add(end);
		}
		
		for (int i = 1; i < N + 1; i++) {
			if(indegree[i] == 0) {
				q.offer(i);
			}
		}
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			sb.append(cur).append(" ");
			for (int i = 0; i < list[cur].size(); i++) {
				int next = list[cur].get(i);
				indegree[next]--;
				if(indegree[next] == 0) {
					q.offer(next);
				}
			}
		}
		
		System.out.println(sb);
	}
}