글 읽기 - java] 런타임에러 발생

xemic 6년 전 0

해당 문제를 플로이드 알고리즘을 활용하여 모든 정점에서 모든 정점까지의 거리를 저장한 다음 모든 거리를 저장한 weight라는 함수에서 가장 최대값을 출력하게 하여 지름을 구하였는데 런타임에러가 발생합니다.

런타임에러 발생 원인에 대한 지적 부탁드립니다.

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void Floid(int w[][], int g[][])
	{
		Stack<Integer> s = new Stack<Integer>();
		for(int i=0; i<w.length; i++) // i is startVertex
		{
			int check[] = new int[w.length];
			s.push(i+1);
			while(!s.isEmpty())
			{
				int temp = s.pop();
				if(check[temp-1]==1)
					continue;
				for(int j=0; j<w.length; j++)
				{
					if(check[j]==0 && g[temp-1][j]!=-1)
					{
						w[i][j] = w[i][temp-1]+g[temp-1][j];
						s.push(j+1);
					}
				}
				check[temp-1] = 1;
			}
		}
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int vertexNum = sc.nextInt();
		int Graph[][] = new int[vertexNum][vertexNum];
		int weight[][] = new int[vertexNum][vertexNum];
		for(int i=0; i<vertexNum; i++)
		{
			for(int j=0; j<vertexNum; j++)
			{
				Graph[i][j] = -1;
				weight[i][j] = 0;
			}
		}
		for(int i=0; i<vertexNum; i++)
		{
			int nowV = sc.nextInt();
			int desV = sc.nextInt();
			int desLen = sc.nextInt();
			Graph[nowV-1][desV-1] = desLen;
			Graph[desV-1][nowV-1] = desLen;
			int nextValue = sc.nextInt();
			while(nextValue != -1)
			{
				desV = nextValue;
				desLen = sc.nextInt();
				Graph[nowV-1][desV-1] = desLen;
				Graph[desV-1][nowV-1] = desLen;
				nextValue = sc.nextInt();
			}
		}
		//okay, now I got every inputData
		Floid(weight, Graph);
		//now you got the answer from the max value of weight array
		int ans=0;
		for(int i=0; i<vertexNum; i++)
		{
			for(int j=0; j<vertexNum; j++)
				ans = weight[i][j]>ans ? weight[i][j] : ans;
		}
		System.out.print(ans);
		
	}
}

djm03178 6년 전 1

vertexNum이 10만이면, Graph와 Weight을 만드는 데에 200억개의 int가 필요합니다. 이는 약 80GB에 해당하는 메모리로, 할당이 가능할 리 없습니다.

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

문제

문제

출처

ICPC

java] 런타임에러 발생

xemic 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말