[BOJ] [JAVA] 2252번 줄 세우기

2252번: 줄 세우기

위상 정렬 문제다. 

사이클이 없는 방향 그래프의 모든 노드들을 순서에 맞춰 정렬하는 알고리즘이다.

노드에 들어오는 간선의 개수인 진입차수가 0인 노드들은 수행할 수 있는 상태의 노드들이므로 큐에 넣는다.

import java.io.BufferedReader;
import java.io.IOException;
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 Main {
	
	static int n;
	static int m;
	static List<Integer>[] graph;
	static StringBuilder sb;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		sb = new StringBuilder();

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		graph = new List[n + 1];
		
		// 진입 차수가 0이면 큐에 삽입한다.
		int[] degree = new int[n + 1];
		
		for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			// p에서 c로 가는 간선을 연결해준다.
			graph[p].add(c);
			degree[c]++;
		}
		
		Queue<Integer> queue = new ArrayDeque<>();
		
		// 초기 상태에서 진입차수가 0인 노드를 모두 큐에 넣는다.
		for (int i = 1; i <= n; i++) {
			if (degree[i] == 0) queue.offer(i);
		}
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			sb.append(cur).append(' ');
			
			// current node와 연결된 노드의 간선을 제거한다.
			for (int next : graph[cur]) {
				degree[next]--;
				
				// next로 진입하는 길이 없다면 큐에 집어넣는다.
				// next를 수강해도 좋다는 뜻.
				if (degree[next] == 0) queue.offer(next);
			}
			
		}
		System.out.println(sb);
	}
}