[KOITP] 위상 정렬

출    처 : http://koitp.org/problem/SDS_PRO_10_2/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	852	217 (25%)	181

문제

DAG(Directed Acyclic Graph)는 방항셩이 있는 간선으로 이루어진 그래프 중, 사이클이 없는 그래프를 의미한다. DAG에서는 위상 정렬을 항상 할 수 있다.

DAG가 주어질 때, 위상 정렬을 하는 프로그램을 작성하시오.

입력

첫 번째 줄에 그래프의 정점의 개수 V, 간선의 개수 E가 공백으로 분리되어 주어진다. (1 ≤ V ≤ 50,000, 1 ≤ E ≤ 100,000)

두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보인 x, y가 공백으로 분리되어 주어진다. 이는 x에서 출발하여 y에 도착하는 유항 간선이 존재한다는 것을 의미한다. (1 ≤ x, y ≤ V, x ≠ y)

주어지는 그래프는 항상 DAG이고, 1번으로 들어오는 간선은 없다.

출력

첫 번째 줄에 위상 정렬의 결과를 출력한다. 답이 여러 가지인 경우, 그 중 아무 것이나 출력한다.

힌트

입력 예제

4 4
1 2
1 3
2 4
3 4

출력 예제

1 2 3 4

혹은

1 3 2 4

< Comment >

 위상 정렬이 뭔가 하고 생각하고 있었는데, Topological Sort를 말하는 것이었다. 실제로 적용하는 과정도 조금 헷갈렸는데 구현 자체는 BFS를 이용하되, 매번 Indegree 를 세어 주기에는 너무 많이 들기 때문에 초기에 Indegree를 세어주고, 하나씩 노드를 없애갈 때마다, 해당 노드에서 나가는 Indegree를 하나씩 없애면서, 0이 될 경우를 체크하여 진행합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Dag {
	
	public static int V = 0;
	public static int E = 0;
	
	public static ArrayList<Integer> adjust[] = null;
	public static boolean isVisited[] = null;
	public static int inDeg[] = null;
	
	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());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		adjust = new ArrayList[V + 1];
		isVisited = new boolean[V + 1];
		inDeg = new int[V + 1];
		
		for (int i = 1 ; i <= V ; i++) {
			adjust[i] = new ArrayList<>();
		}
		
		int num1 = 0;
		int num2 = 0;
		for (int i = 0 ; i < E ; i++) {
			st = new StringTokenizer(br.readLine());
			num1 = Integer.parseInt(st.nextToken());
			num2 = Integer.parseInt(st.nextToken());
			
			adjust[num1].add(num2);
			inDeg[num2]++;
		}
		
		BFS();


		bw.flush();
		bw.close();
	}
	
	public static void BFS() {
		
		ArrayDeque<Integer> q = new ArrayDeque<>();
		
		
		for (int i = 1 ; i <= V ; i++) {
			
			if (inDeg[i] == 0) {
				q.addLast(i);
			}
		}
		
		
		while(!q.isEmpty()) {
			
			int node = q.pollFirst();
			isVisited[node] = true;
			
			System.out.print(node + " ");
			for (int to : adjust[node]) {
			
				inDeg[to]--;
				if (!isVisited[to] && inDeg[to] == 0) {
					q.add(to);
				}	
			}
		}
	}
}