[알고리즘] 위상정렬(Topological Sort)이란?

1. 위상정렬이란?

: 유향 그래프의 꼭짓점을 방향을 거스르지 않도록 나열하는 것

: 위상 정렬을 이해하기 쉽게 표현하면 대학교의 선수과목이 있다.

: B라는 과목을 듣기 위해 A라는 과목이 선행 학습 되어야 할 때 올바른 수강 순서를 찾아낼 수 있다.

 

2. 코드

: 첫째 줄에는 요소의 수와 선행 관계의 수가 주어진다.

: 그 다음 선행관계들이 주어진다.

: 이 때 해당 요소에 도달하기 위해 선행되어야 하는 요소들의 수를 indegree 배열에 누적에서 더한다.

: indegree의 수가 0인 것부터 차례대로 순회할 수 있도록 한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		ArrayList<Integer>[] adj = new ArrayList[N+1];
		int[] indegree = new int[N+1];
		for(int i = 1; i < N+1; i++) adj[i] = new ArrayList<>();
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			adj[from].add(to);
			indegree[to]++;
		}
		
		Queue<Integer> q = new LinkedList<>();
		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, size = adj[cur].size(); i < size; i++) {
				int sub = adj[cur].get(i);
				indegree[sub]--;
				if(indegree[sub] == 0) q.offer(sub);
			}
		}
		System.out.println(sb);
	}
}