[Baekjoon] 2252번: 줄 세우기

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

문제 설명

위상 정렬 기초 문제이다. 위상 정렬(Topology Sort)는 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 자세한 설명은 위상 정렬을 다룬 글에서 찾아보자.

풀이 방법

위상 정렬을 구현만 하면 해결할 수 있는 문제이다.

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

class Main {

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    static int[] indegree;

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

        String[] split = br.readLine().split(" ");

        int N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);

        indegree = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            split = br.readLine().split(" ");
            int a = Integer.parseInt(split[0]);
            int b = Integer.parseInt(split[1]);

            graph.get(a).add(b);
            indegree[b]++;
        }

        System.out.println(topologySort());
    }

    private static String topologySort() {
        ArrayList<Integer> result = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();

        for (int i = 1; i < indegree.length; i++) {
            if (indegree[i] == 0)
                q.offer(i);
        }

        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            Integer now = q.poll();
            result.add(now);
            ArrayList<Integer> list = graph.get(now);

            for (int i : list) {
                indegree[i]--;
                if (indegree[i] == 0)
                    q.offer(i);
            }
        }

        for (Integer i : result) {
            sb.append(i).append(" ");
        }

        return sb.toString();
    }
}