BOJ 2252 줄 세우기 [Java]

문제

BOJ 2252 줄 세우기

접근방법

• 위상정렬의 대표적인 문제이다.
• 진입차수라는 개념을 알면 쉽다.
• 이 문제에서의 진입차수 : 자신을 가르키는 화살표의 개수 (자신보다 작다고 판별된 사람 수)
• n^2 크기의 정수형 배열을 만들어서 화살표 정보를 넣으려고 했지만 처음에는 메모리 초과가 떴다...
• 그래서 ArrayList로 동적할당을 하였더니 통과하였다.
• 단순히 배열이 ArrayList보다 메모리가 작을거라고 생각했지만, 쓸데없는 공백이 많이 만들어질 것 같은 경우에는 ArrayList로 풀이하는 것이 훨씬 효율적인 것 같다.

구현

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

public class Main {
    static int N, M;
    static int[] indegree;
    static ArrayList<ArrayList<Integer>> edges = new ArrayList<>();
    static Queue<Integer> q;

    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ", false);

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        indegree = new int[N+1];
        q = new LinkedList<>();

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ", false);
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            indegree[end]++;
            edges.get(start).add(end);
        }

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

        while(!q.isEmpty()) {
            int num = q.poll();

            bw.write(num+" ");

            for (int i = 0; i < edges.get(num).size(); i++) {
                int curr = edges.get(num).get(i);
                indegree[curr]--;
                if(indegree[curr] == 0) q.add(curr);
            }
        }

        bw.close();
    }
}

제출