[Java/Topological Sort] 백준 2252. 줄세우기

🤔 Intuition

* 그래프를 활용할 것이라는 건 명확했지만, 위상정렬을 잘 몰라서 유니온 파인드로 접근하다가 데였다.
* 정렬을 어떻게 하지? 하는 생각을 바탕으로 유니온 파인드만 써서 지저분하게 풀다가 "이거 안되는건가?" 하고 알아봤는데 위상정렬이었다.
* 위상정렬이라는 유형이 존재하며, inDegree를 이용한 알고리즘을 한번 학습한 적은 있었지만 체화가 안되어있었다.
* 최빈출 유형은 아니지만, 그래도 기왕 보게 된 김에 알아두자.

 * 알고보니 위상정렬 대표유형 문제... 어쩐지 정답률이 높더라

🔎 Algorithm & Complexity

 * @algorithm topological sort
 * @time O(N + M) ; indegree활용 위상정렬 - 노드개수 N, 간선개수 M -> 524 ms
 * @memory O(N + M) ; 노드 개수만큼 inDegree 배열 운영 + 간선 리스트 운영 -> 51944 KB

👨🏻‍💻 Logic

그냥 위상정렬 알고리즘 적용하면 된다.

public class Main {
    private static int N, M;
    private static ArrayList<Integer>[] adj;
    private static int[] inDegree;
    private static ArrayDeque<Integer> q = new ArrayDeque<>();
    private static ArrayDeque<Integer> ans = new ArrayDeque<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        inDegree = new int[N+1];
        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj[b].add(a);
            inDegree[a]++;
        }

        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                q.add(i);
            }
        }

        while (!q.isEmpty()) {
            int v = q.poll();
            ans.addLast(v);
            for (int u : adj[v]) {
                inDegree[u]--;
                if (inDegree[u] == 0) {
                    q.add(u);
                }
            }
        }
        while (!ans.isEmpty()) {
            sb.append(ans.pollLast()+" ");
        }
        System.out.println(sb.toString());
    }
}