P.2252 줄 세우기

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {

    static int n, m;
    static ArrayList<Integer>[] graph;
    static int[] depth;

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; m = line[1];
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
        depth = new int[n + 1];
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            graph[line[0]].add(line[1]);
            depth[line[1]]++;
        }

        topologicalSort();

        bw.flush();
    }

    private static void topologicalSort() throws IOException {
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (depth[i] == 0) queue.add(i);
        }

        while (!queue.isEmpty()) {
            Integer poll = queue.poll();

            bw.write(poll + " ");

            for (Integer integer : graph[poll]) {
                depth[integer]--;

                if (depth[integer] == 0) queue.add(integer);
            }
        }
    }
}

코드 설명

처음에는 삽입 정렬과 같은 정석적인 정렬 알고리즘을 생각했는데 학생들 각각을 정점으로 보게 된다면 위상 정렬이 생각나는 문제였다.

 

두 학생의 키를 비교한 입력(A B)에서 B는 진입 차수가 1인 정점이 된다.

모든 입력을 받은 후에 각 정점의 진입 차수를 알게 되고 위상 정렬 알고리즘을 사용하면 진입 차수가 0인 정점들을 꺼내 정렬할 수 있으므로 키 순서대로 정렬할 수 있다.

 

위상정렬에 대한 알고리즘은 다음 글에 정리되어 있다.

2023.08.23 - [코딩테스트/백준] - P.1005 ACM Craft

P.1005 ACM Craft