백준 - 1766번 문제집

https://www.acmicpc.net/problem/1766

접근법

기본적인 위상정렬문제로 해결
1. graph라는 List배열을 할당해주고,
2. 각각 인덱스에 후속작업의 인덱스를 넣어줌. graph[pre].add(post)
넣어주면서, 전 작업이 필요한 경우 count를 올려줌. inDegree[post]++

4번은 1번 앞에 있어야함 => graph(1).add(4),
5번은 1번 앞에있어야함 => graph(1).add(5)

3. inDegree의 값이 0인 인덱스에 대해 우선순위 큐에 삽입
   (문제에서 숫자가 빠른순으로 처리하라는 내용이 있으므로 우선순위 큐를 사용함)
4. 우선순위 큐에 맞게 꺼낸 항목에 대해, 후속작업 List를 탐색하고 각각에 대해 inDegree count를 낮춤
   4-1. inDegree 값이 0이면 큐에 삽입하여, 큐가 없을때 까지 진행

소스

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static ArrayList<Integer>[] graph;
	static int[] inDegree;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		graph = new ArrayList[N+1];
		inDegree = new int[N+1];
		for(int i = 1; i < N+1; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int pre = Integer.parseInt(st.nextToken());
			int post = Integer.parseInt(st.nextToken());
			
			graph[pre].add(post);
			inDegree[post]++;
		}
		topologicalSort();
		
	}
	static void topologicalSort() {
		PriorityQueue<Integer> q = new PriorityQueue<Integer>();
		
		for(int i = 1; i < N+1; i++) {
			if(inDegree[i] == 0) q.offer(i);
		}
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			System.out.println(cur);
			
			for(int i = 0; i < graph[cur].size(); i++) {
				int link = graph[cur].get(i);
				inDegree[link]--;
				if(inDegree[link] == 0) q.offer(link);
			}
			
		}
	}
}