[BaekJoon] 1766 문제집 (java)

🔗 문제 링크

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

👨🏻‍💻 작성한 코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		int[] inDegree = new int[n+1]; // node로 연결된 node의 수
		
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		
		// n개의 문제 추가
		for (int i=0; i<=n; i++) {
			list.add(new ArrayList<Integer>());
		}
		
		for (int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int problem1 = Integer.parseInt(st.nextToken());
			int problem2 = Integer.parseInt(st.nextToken());
			
			list.get(problem1).add(problem2);

			inDegree[problem2]++;
		}
		
		for(int i=1; i<=n; i++) {
			if(inDegree[i] == 0)
				queue.offer(i);
		}
		
		while (!queue.isEmpty()) {
			int problem = queue.poll();
			bw.write(problem+" ");
			for (int i: list.get(problem)) {
				inDegree[i]--;
				if (inDegree[i] == 0) {
					queue.offer(i);
				}
			}
		}
	
		bw.flush();
		bw.close();
	
	}
}

📝 위상 정렬(Topology Sort) 알고리즘

1. 진입 차수가 0인 정점을 Queue에 삽입한다.
2. Queue에서 원소를 꺼내 해당 원소와 간선을 제거한다.
3. 제거 이후 진입 차수가 0이 된 정점을 Queue에 삽입한다.
4. Queue가 빌 때까지 2,3과정을 반복한다.

이때 Queue에서 나온 순서가 위상 정렬의 결과가 된다.

이때 모든 원소를 방문하기 전에 큐가 비는 일이 발생한다면 해당 그래프에는 사이클이 존재하는 것이다.
※ 사이클이 존재한다는 것은 A가 해결되어야 B가 해결될 수 있고 B가 해결되어야 A를 해결할 수 있다는 것을 의미하여 둘 다 수행을 할 수 없는 것이다.