기초 - 위상 정렬

위상정렬

'순서가 정해져있는 작업'을 차례로 수행해야 할 때 순서를 결정해 주기 위한 알고리즘 입니다.

🚨사이클이 발생 하는 경우에는 위상정렬 사용할 수 없음. 위상정렬은 시작점이 존재해야한다.

1. 진입 차수가 0인 정점을 Queue에 삽입.
2. Queue에서 꺼낸 원소의 노드와 연결된 간선을 제거합니다.
3. 이때 간선 제거 이후에 진입차수가 0이 된 정점을 Queue에 삽입합니다.
4. Queue가 빌때까지 반복하고, 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재 하는 것이고, Queue에서 꺼낸 순서가 위상정렬의 결과입니다.

🚨모든 노드의 차수는 0이라고 초기화 하기.

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

public class 위상정렬 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		int d[] = new int[V+1];
		for(int i = 0; i <= V; i++) {
			d[i] = 0;
			list.add(new ArrayList<>());
		}
		
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			d[b]++;
			list.get(a).add(b);
		}
		
		Queue<Integer> q = new LinkedList<>();
		
		for(int i = 1; i <= V; i++) {
			if(d[i] == 0)
				q.add(i);
		}
		
		StringBuilder sb = new StringBuilder();
		
		while(!q.isEmpty()) {
			int N = q.poll();
			sb.append(N + " ");
			
			for(Integer n : list.get(N)) {
				if(--d[n] == 0) {
					q.add(n);
				}
			}
		}
		System.out.println(sb.toString());
	}

}