[백준] [JAVA] 줄세우기 2252 위상정렬 메모리 초과

위상정렬이란 정해진 순서가 있고 해당 순서대로 정렬한 것을 의미한다.
정해진 순서란 작업들 간의 관계이다. 
즉 의존하고 있는 작업이 반드시 의존 되고 있는 작업보다 뒤에와야 한다.
예를들어 A가 B를 의존하고 있다고 가정하면 
B A 순서여야한다. 
1학년 때 알고리즘 기초를 수강해야 2학년때 알고리즘 심화를 들을 수 있는 것과 같다.

 

위상정렬은 인접행렬과 인접리스트로 구현할 수 있는데 
이때 인접행렬은 시간복잡도가 O(V^2) 이고 공간 복잡도도 마찬가지이다 
하지만 인접리스트는 시간복잡도가 O(V+E) 이며 공간 복잡도는 O(V+E)이다 

인접 행렬을 사용하여 메모리가 초과가 난 코드 

32000 * 32000 *4 거의 4000MB를 사용하게 되어 메모리 초과가 발생한다.
시간 복잡도도 1초를 넘길 수 있다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static List<Integer> dfsOrder = new ArrayList<>();

    static ArrayList<ArrayList<Integer>> dfs = new ArrayList<>();
    static int[] check;
    static int n;

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

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        ArrayList<Integer> bigs = new ArrayList<>();

        for (int i = 0; i < n + 1; i++) {
            dfs.add(new ArrayList<>());
        }


        check = new int[n + 1];
        for (int i = 0; i < m; i++) {
            String[] input2 = br.readLine().split(" ");
            int big = Integer.parseInt(input2[0]);
            int small = Integer.parseInt(input2[1]);
            dfs.get(big).add(small);
            bigs.add(big);
        }
        for (Integer big : bigs) {
            DFS(big);
        }
        Collections.reverse(dfsOrder);

        for (Integer number : dfsOrder) {
            bw.write(number + " ");
        }
        for (int i = 1; i < n + 1; i++) {
            if (check[i] == 0) bw.write(i + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static void DFS(int big) {
        if (check[big] != 0) return;
        for (Integer small : dfs.get(big)) {
            DFS(small);
        }
        check[big] = 1;
        dfsOrder.add(big);
    }
}

 

인접리스트를 사용하게 된다면 
최대 간선의 개수가 100000이고 정점이 최대 32000개이므로 
아무리 넉넉히 잡아도 10MB면 처리가 가능하다.

 

package 백준;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class 줄세우기2252 {
    static List<Integer> dfsOrder = new ArrayList<>();

    static ArrayList<ArrayList<Integer>> dfs = new ArrayList<>();
    static int[] check;
    static int n;

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

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        ArrayList<Integer> bigs = new ArrayList<>();

        for (int i = 0; i < n + 1; i++) {
            dfs.add(new ArrayList<>());
        }


        check = new int[n + 1];
        for (int i = 0; i < m; i++) {
            String[] input2 = br.readLine().split(" ");
            int big = Integer.parseInt(input2[0]);
            int small = Integer.parseInt(input2[1]);
            dfs.get(big).add(small);
            bigs.add(big);
        }
        for (Integer big : bigs) {
            DFS(big);
        }
        Collections.reverse(dfsOrder);

        for (Integer number : dfsOrder) {
            bw.write(number + " ");
        }
        for (int i = 1; i < n + 1; i++) {
            if (check[i] == 0) bw.write(i + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static void DFS(int big) {
        if (check[big] != 0) return;
        for (Integer small : dfs.get(big)) {
            DFS(small);
        }
        check[big] = 1;
        dfsOrder.add(big);
    }
}

 

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