[백준(Baekjoon)][자바(java)] 14567 : 선수과목 (Prerequisite) / 위상 정렬

 

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

14567번: 선수과목 (Prerequisite)

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static List<List<Integer>> edge_out;
	static int[] degree_in;

	static String topologicalSort(int n) {
		Queue<Integer> top = new LinkedList<>();
		int answer[] = new int[n], i, u, lv = 0;
		boolean visited[] = new boolean[n];
		do {
			if (top.isEmpty()) {
				lv++;
				for (i = 0; i < n; ++i) {
					if (!visited[i] && degree_in[i] == 0) {
						top.add(i);
						answer[i] = lv;
						visited[i] = true;
					}
				}
				if (top.isEmpty()) break;
			}
			u = top.remove();
			for (int v : edge_out.get(u))
				degree_in[v]--;
		} while (true);
		StringBuilder sb = new StringBuilder();
		for (i = 0; i < n; ++i)
			sb.append(answer[i] + " ");
		return sb.toString();
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), i, u, v;
		edge_out = new ArrayList<>();
		for (i = 0; i < n; ++i)
			edge_out.add(new ArrayList<>());
		degree_in = new int[n];
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken()) - 1;
			v = Integer.parseInt(st.nextToken()) - 1;
			edge_out.get(u).add(v);
			degree_in[v]++;
		}
		br.close();

		System.out.print(topologicalSort(n));
	}
}

 

( 위상 정렬  :  https://hyunjiishailey.tistory.com/361 )