글 읽기 - 1753 다익스트라 알고리즘 메모리 초과

palatable7 5년 전 0

다익스트라 알고리즘으로 작성했지만, 메로리 초과가 계속 일어납니다. 전역변수를 지역변수로 바꾸어도 여전히 메모리초과가 이어집니다.

메모리 초과의 원인이 되는 곳은 어떤 곳일까요?

import java.util.Scanner;

public class Main {
	int n, m, count;
	int[][] arr;
	int[] visited;
	int[] length;
	int vnear;
	
	String[] line;
	Scanner sc = new Scanner(System.in);
	static final int INF = 654321;
	
	void main() {

		line = sc.nextLine().split(" ");
		n = Integer.parseInt(line[0]);
		m = Integer.parseInt(line[1]);

		line = sc.nextLine().split(" ");
		int start = Integer.parseInt(line[0]);
		
		arr = new int[n][n];
		for(int i = 0;i<n;i++)
			for(int j=0;j<n;j++)
				arr[i][j]=INF;
		
		for (int i = 0; i < m; i++) {
			line = sc.nextLine().split(" ");
			int t1 = Integer.parseInt(line[0])-1;
			int t2 = Integer.parseInt(line[1])-1;
			arr[t1][t2] = Integer.parseInt(line[2]);
		}
		
		dijkstra(start-1);
		System.out.println(0);
		for(int i=1;i<n;i++) {
			if(length[i] != INF)
				System.out.println(length[i]);
			else
				System.out.println("INF");
		}
	}
	
	void dijkstra(int i) {
		visited=new int[n];
		visited[i]=1;
		
		length=new int[n];
		for(int q = 0;q<n;q++)
			length[q]=arr[i][q];

		int repeat = n;
		while(repeat-- != 0) {
			int min = INF;
			for(int a = 0 ;a <n;a++) {
				if(visited[a] ==0 && length[a] < min) {
					min = length[a];
					vnear = a;
				}
				visited[vnear]=1;
			}
			
			for(int a = 0; a<n;a++) {
				if(length[a] > length[vnear] + arr[vnear][a]) {
					length[a]=length[vnear] + arr[vnear][a];
				}
			}
		}
	}

	public static void main(String[] args) {
		new Main().main();
	}
}

fhskf94kr 5년 전 2

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000).

라는 조건과

23번째 라인을 보시면 알 수 있습니다.

V가 최댓값일 때, int형 2차원 배열 arr의 크기는 얼마일까요?

palatable7 5년 전 0

아 그걸 생각 못했네요. 감사합니다.

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

문제

문제

출처

ICPC

1753 다익스트라 알고리즘 메모리 초과

palatable7 5년 전 0

fhskf94kr 5년 전 2

palatable7 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말