글 읽기 - 다익스트라 메모리 초과 도와주세요..ㅠㅠ(코드 있음!)

geesuee 2년 전 1

다익스트라 문제를 풀어보고 있습니다.

다른 문제 코드를 기반으로 응용해서 이 문제를 풀어보려고 했는데 계속 메모리 초과가 뜹니다ㅜ

1) N,M 등의 값이 엄청 커졌을 때, 제 코드에 반복문이 너무 많아서 메모리 초과가 나는 것일까요..?

2) 아니면 제가 찾지 못한 특정 반례에서 오버플로우가 나는 걸까요??ㅜㅠ

(질문 게시판에 K=0인 것, 출발점 노드의 비용 배열 값을 0으로 하면 안된다는 글을 확인해서 그 부분 수정했음에도 여전히 메모리 초과입니다..)

3) 다른 분들 풀이를 찾아봤는데 큐를 활용한 풀이가 많았습니다. 이 문제는 큐를 활용해서 풀어야 메모리 초과가 나지 않는 것인가요..?

최대한 제 힘으로 해결해보려고 했는데 실패했습니다..ㅜ 도와주시면 감사드리겠습니다!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int K;
    static int X;
    static int[][] map;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        map = new int[N+1][N+1];

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = 1;
        }

        System.out.println(dijkstra(X, K));

//        for(int[] m : map) {
//            for(int a : m) {
//                System.out.print(a + " ");
//            }
//            System.out.println();
//        }
    }

    public static String dijkstra(int X, int K) {
        int cost[] = new int[N+1]; // 비용 저장 배열
        boolean[] visited = new boolean[N+1]; // 방문 여부 저장 배열

        // cost 값 초기화(최대값으로)
        for(int i = 1; i < N+1; i++) {
            cost[i] = Integer.MAX_VALUE;
        }

        // 시작 노드 값 초기화
        cost[X] = Integer.MAX_VALUE;
        visited[X] = true;

        // 연결된 노드 cost 값 갱신
        List<Integer> linked_index = new ArrayList<>();
        for(int i = 1; i < N+1; i++) {
            if(!visited[i] && map[X][i] == 1) {
                cost[i] = 1;
                linked_index.add(i);
            }
        }

        // 최소 cost 값 갱신
        for(int idx : linked_index) {
            visited[idx] = true;

            for(int i = 1; i < N+1; i++) {
                if(!visited[i] && map[idx][i] == 1) {
                    if(cost[i] > cost[idx] + map[idx][i]) {
                        cost[i] = cost[idx] + map[idx][i];
                    }
                }
            }
        }

        // 결과값 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < N+1; i++) {
            if(cost[i] == K) {
                sb.append(i + "\n");
            }
        }

        return sb.length()!=0? sb.toString():"-1";
    }
}

djm03178 2년 전 4

메모리 초과는 할당 받으려고 한 메모리가 너무 클 때 받게 됩니다. 반복문이 많이 도는지, 오버플로우가 나는지 등과는 무관합니다.

이 코드의 문제점은 간선 정보를 인접 행렬로 저장하고 있다는 점입니다. 24번째 줄은 N이 30만일 때 약 900억 개의 int형을 할당받으려고 하는데, int형 하나당 4바이트씩 계산하면 3600억 바이트 ~= 34만 메가바이트로 이 문제의 메모리 제한인 256메가바이트에 자바 보너스를 합한 528메가바이트의 약 650배 많은 메모리를 할당받으려고 시도하게 됩니다. 이렇게 많은 메모리를 할당받는 것을 문제에서 허용하지 않으므로 메모리 초과를 받게 됩니다.

인접 행렬이 아닌 인접 리스트로 만들어야 이런 문제를 피할 수 있습니다.

geesuee 2년 전 0

아아 그렇군요!! 친절한 답변 감사합니다!! 시도해보겠습니다 감사합니다!!

geesuee 2년 전 0

말씀해주신대로 인접리스트로 수정해보았습니다 감사합니다!

인접 리스트로 수정하니 더이상 메모리 초과가 뜨지 않습니다!

그런데...이번에는 틀렸다고 나옵니다ㅜ

테스트 케이스는 다 제대로 나왔는데 어느 부분이 문제인지 모르겠습니다.

혹시 다른 테스트 케이스가 있을까요..?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N,M,K,X;
    static ArrayList<Integer>[] map;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

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

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

        System.out.println(dijkstra(X, K));
    }

    public static String dijkstra(int X, int K) {
        int cost[] = new int[N+1]; // 비용 저장 배열
        boolean[] visited = new boolean[N+1]; // 방문 여부 저장 배열

        // cost 값 초기화(최대값으로)
        for(int i = 1; i < N+1; i++) {
            cost[i] = Integer.MAX_VALUE;
        }

        // 시작 노드 값 초기화
        cost[X] = Integer.MAX_VALUE;
        visited[X] = true;

        // 연결된 노드 cost 값 갱신
        List<Integer> linked_index = new ArrayList<>();
        for(int i = 1; i < N+1; i++) {
            if(!visited[i] && map[X].contains(i)) {
                cost[i] = 1;
                linked_index.add(i);
            }
        }

        // 최소 cost 값 갱신
        for(int idx : linked_index) {
            visited[idx] = true;

            for(int i = 1; i < N+1; i++) {
                if(!visited[i] && map[idx].contains(i)) {
                    if(cost[i] > cost[idx] + 1) {
                        cost[i] = cost[idx] + 1;
                    }
                }
            }
        }

        // 결과값 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < N+1; i++) {
            if(cost[i] == K) {
                sb.append(i + "\n");
            }
        }

        return sb.length()!=0? sb.toString().trim():"-1";
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다익스트라 메모리 초과 도와주세요..ㅠㅠ(코드 있음!)

geesuee 2년 전 1

djm03178 2년 전 4

geesuee 2년 전 0

geesuee 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말