백준 2252 - 줄 세우기

접근

일부 학생들의 키만을 비교한 후 줄을 세우고, 답이 여러가지인 경우가 있다는 점에서 위상정렬이라는 것을 알 수 있다.

위상정렬이란?

유한 그래프의 정점들을 방향을 거스르지 않도록 나열하는 것.
차례대로 무언가를 수행하거나 무언가를 세울 때, 순서를 결정해주는 알고리즘이다.

풀이

위상정렬 문제는 유향그래프를 생성하며 각 정점의 진입차수를 세어준 후, 진입차수가 0인 정점부터 QUEUE에 넣어 하나씩 탐색하면 된다.
이 때, 각 정점을 탐색할 때는 해당 정점과 연결된 정점의 진입차수를 하나씩 낮춰준 후 진입차수가 0이 된 정점들을 다시 QUEUE에 넣어 탐색해주면 된다.

정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws Exception {
    	//입력받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		
		int n = Integer.parseInt(str[0])+1;
		int m = Integer.parseInt(str[1]);
		StringBuilder sb = new StringBuilder();
		
        //유향 그래프를 인접 리스트 형태로 구현
		ArrayList<Integer>[] graph = new ArrayList[n];
		for(int i = 0; i < n; i++) {
			graph[i] = new ArrayList<>();
		}
		int[] inputs = new int[n];
		int a, b;
		for(int i = 0; i < m; i++) {
			str = br.readLine().split(" ");
			a = Integer.parseInt(str[0]);
			b = Integer.parseInt(str[1]);
			
            //입력받은 정점의 진입차수를 하나씩 높혀준다
			inputs[b] = inputs[b]+1;
			graph[a].add(b);
		}
		
        //진입차수가 0인 정점들을 Queue에 넣기
		Queue<Integer> que = new LinkedList<Integer>();
		for(int i = 1; i <n;i++) {
			if(inputs[i] == 0) {
				que.add(i);
			}
		}
		
        //Queue에 넣은것을 하나씩 탐색하며 연결된 정점의 진입차수를 1씩 줄임
		int size;
		while(!que.isEmpty()) {
			a = que.poll();
			sb.append(a).append(" ");
			size = graph[a].size();
			for(int i = 0; i < size;i++) {
				--inputs[graph[a].get(i)];
				if(inputs[graph[a].get(i)] == 0) {
					que.add(graph[a].get(i));
				}
			}
		}
		System.out.println(sb);
	}

}