Algorithm 19일차

알고리즘에서 위상 정렬을 활용할 수 있다.

순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정하는 걸 위상 정렬이라 한다.

아래는 그 예시를 보여준다.

미리 정의된 과목의 순서를 지키며 정렬이 되어있는 걸 확인할 수 있다.

위상 정렬은 선후 관계가 정의된 그래프 구조에서 활용될 수 있다.
따라서 위상 정렬이 성립하기 위해서는 그래프가 반드시 비순환 유향 그래프여야 한다.

위상 정렬은 BFS를 사용하여 구현한다. 구현 방법은 아래와 같다.

1. 진입 차수가 0인 노드(시작점 가능)를 큐에 모두 넣는다.
2. 큐에서 노드를 꺼내 위상 정렬에 넣는다.
3. 꺼낸 노드와 인접한 노드의 진입 차수를 1 감소시킨다.
4. 1, 2, 3번 과정을 큐가 빌 때까지 반복한다.

이 때 모든 노드가 위상 정렬에 포함되어 있다면 위상 정렬이 완성된 것이고,
모든 노드가 위상 정렬에 포함되어 있지 않다면 사이클이 발생한 것이다.

이를 Node 클래스로 구현하면 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class TopologySortTest {
	static int N;
	static int M;
	static Node[] adjList;
	static int[] inDegree; // 진입차수 관리
	
	static class Node {
		int vertex;
		Node link;
		
		public Node(int vertex, Node link) {
			super();
			this.vertex = vertex;
			this.link = link;
		}
	}
	
	static ArrayList<Integer> topologySort() {
		Queue<Integer> queue = new ArrayDeque<>();
		ArrayList<Integer> orderList = new ArrayList<>();
		
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == 0) {
				queue.offer(i);
			}
		}
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			orderList.add(cur);
			
			for (Node temp = adjList[cur]; temp != null; temp = temp.link) {
				if (inDegree[temp.vertex] - 1 == 0) {
					queue.offer(temp.vertex);
				}
				
				
			}
			
		}
		
		return orderList;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		adjList = new Node[N];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			adjList[from] = new Node(to, adjList[from]);
			inDegree[to]++;
		}
		
		List<Integer> list = topologySort();
		
		if (list.size() == N) {
			for (int vertex : list) {
				System.out.println(vertex + " ");
			}
		} else {
			System.out.println("cycle");
		}
	}
}