[백준] 줄 세우기

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다.
일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

풀이

위상 정렬의 대표 유형이다.
사이클이 없는 방향 그래프(DAG: Directed Acyclic Graph)에서, 각 Vertex 들의 선행 순서를 위배하지 않으면서 모든 Vertex를 나열하는 것이 위상 정렬이다.
즉 방향 그래프를 순차적으로 나열했다는 뜻이다.

[위상 정렬의 특징]

• 하나의 방향 그래프에는 여러 위상 정렬이 가능하다.
• 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 한다.
• 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N; // 그래프 정점의 수
	static int M; // 간선의 수

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
//정점에 연결된 간선 수 
		int[] cntOfLink = new int[N + 1];
		ArrayList<ArrayList<Integer>> g = new ArrayList<>();

		for (int i = 0; i < N + 1; i++) {
			g.add(new ArrayList<>());
		}
		// 간선 추가
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			//directed_add_edge
            g.get(a).add(b);
			cntOfLink[b]++; //후생 정점 간선수 증가 ~ 
		}
		//위상 정렬 (A --> B  순서 ) 
		topologicalSort(g, cntOfLink);
		
	}

	static void topologicalSort(ArrayList<ArrayList<Integer>> graph, int[] cntOfLink) {
		Queue<Integer> queue = new LinkedList();

		// 초기: 선행 정점을 가지지 않는 정점을 큐에 삽입
		for (int i = 1; i < N + 1; i++) {
			if (cntOfLink[i] == 0) { // 해당 정점의 간선의 수가 0이면
				queue.add(i);
			}
		}
		StringBuilder sb = new StringBuilder();
		
		// 정점의 수 만큼 반복
		for (int i = 0; i < N; i++) {
			int v = queue.remove(); // 1. 큐에서 정점 추출
			sb.append(v).append(" ");

			// 2. 해당 정점과 연결된 모든 정점에 대해
			for (int nextV : graph.get(v)) {
				cntOfLink[nextV]--; // 2-1. 간선의 수 감소

				// 2-2. 선행 정점을 가지지 않는 정점을 큐에 삽입
				if (cntOfLink[nextV] == 0) { // 해당 정점의 간선의 수가 0이면
					queue.add(nextV);
				}
			}
		}
        //print_answer
	System.out.println(sb.toString());
		
	}
}