[Baekjoon Online Judge] 2252번: 줄 세우기

2252번: 줄 세우기

요구사항

 - N명의 학생들을 키 순서대로 줄을 세우려고 한다.

 - 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다.

 - 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

입력

 - 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다.

 - M은 키를 비교한 회수이다.

 - 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다.

 - 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

 - 학생들의 번호는 1번부터 N번이다.

출력

 - 첫째 줄부터 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

---

위상정렬

참고 : gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Baekjoon2252 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String[] input = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        List<Integer>[] lists = new LinkedList[n + 1]; // 노드의 연결 상태를 저장
        int[] edges = new int[n + 1]; // 간선의 개수 저장

        for (int i = 1; i <= n; i++) lists[i] = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            input = bufferedReader.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            lists[a].add(b);
            edges[b]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++)
            if (edges[i] == 0) queue.offer(i);

        StringBuilder stringBuilder = new StringBuilder();
        while (!queue.isEmpty()) {
            int now = queue.poll();
            stringBuilder.append(now + " ");

            for (Integer index : lists[now]) {
                edges[index]--;
                if (edges[index] == 0) queue.offer(index);
            }
        }

        System.out.println(stringBuilder.toString());
        bufferedReader.close();
    }
}