[BOJ] 2252. 줄 세우기

문제 원본 : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Graph graph = new Graph(n);
        for (int i = 0; i < m; ++i) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph.add(a - 1, b - 1);
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (Integer v : graph.vertex) {
            if (graph.inDegree.getOrDefault(v, 0) == 0) {
                queue.add(v);
            }
        }

        List<Integer> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            int v = queue.poll();
            ans.add(v);

            for (Node node : graph.graph.get(v)) {
                int cnt = graph.inDegree.get(node.to);
                if (cnt - 1 == 0) {
                    queue.add(node.to);
                }

                graph.inDegree.put(node.to, cnt - 1);
            }
        }

        StringBuilder builder = new StringBuilder();
        boolean[] visit = new boolean[n];
        for (Integer i : ans) {
            builder.append(i + 1).append(" ");
            visit[i] = true;
        }

        for (int i = 0; i < n; ++i) {
            if (!visit[i]) {
                builder.append(i + 1).append(" ");
            }
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }

    public static class Graph {
        public List<List<Node>> graph;
        public Set<Integer> vertex;
        public Map<Integer, Integer> inDegree;

        public Graph(int num) {
            this.vertex = new HashSet<>();
            this.inDegree = new HashMap<>();
            this.graph = new ArrayList<>(num);
            for (int i = 0; i < num; ++i) {
                this.graph.add(new ArrayList<>());
            }
        }

        public void add(int from, int to) {
            vertex.add(from);
            vertex.add(to);

            int cnt = inDegree.getOrDefault(to, 0);
            inDegree.put(to, cnt + 1);

            graph.get(from).add(new Node(from, to));
        }
    }

    public static class Node {
        public int from;
        public int to;

        public Node(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }
}

• 위상 정렬 기본 문제
• 위상 정렬은 처음 풀어봐서 인강을 듣고 풀었다.
• 내부 클래스는 인강을 참고했다.
• 그냥 배열로 구현하면 내부 클래스는 구현할 필요가 없다.