글 읽기 - [Java] RunTime 오류 발생

javabank123 7년 전 0

안녕하세요.

Sample Input 에 대한 출력값은 정상적으로 나오는데, 실제 제출시 RunTime 오류가 발생하고 있습니다.

어느부분이 문제인지 감이 오지 않아, 고수님들의 도움을 요청 드립니다.

힌트라도 주시면 감사요..^^

import java.util.Scanner;

public class Main {

	static int[][] map;
	static int[] dist;
	static boolean[] visit;
	static int nE, nV, start;
	static final int INF = Integer.MAX_VALUE - 9;

	public static void search(int start) {
		dist[start] = 0; 
		for (int i = 1; i <= nV; i++) 
		{
			int min = INF; 
			int index = -1;
			for (int j = 1; j <= nV; j++) {
				if (visit[j] == false && min > dist[j] - 1) { 
					min = dist[j];
					index = j;
					/*
					 * System.out.println("min:" + min);
					 * System.out.println("index:" + index);
					 */
				}
			}
			visit[index] = true;
			// System.out.println("visited:" + Arrays.toString(visit));

			for (int k = 1; k <= nV; k++) {
				if (map[index][k] != 0 && dist[k] > dist[index] + map[index][k]) { 
					dist[k] = dist[index] + map[index][k];
					// System.out.println("dist:" + Arrays.toString(dist));
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		nV = scan.nextInt();
		nE = scan.nextInt();
		start = scan.nextInt();

		map = new int[nV + 1][nV + 1];
		dist = new int[nV + 1];
		visit = new boolean[nV + 1];

		for (int i = 1; i <= nV; i++) {
			dist[i] = INF; // 임의의 무한한 값으로 거리값 초기화
		}

		for (int i = 0; i < nE; i++) {
			int t1 = scan.nextInt();
			int t2 = scan.nextInt();
			int t3 = scan.nextInt();

			map[t1][t2] = t3;
		}

		// printMap();

		search(start);

		for (int i = 1; i <= nV; i++) {
			if (dist[i] == INF)
				System.out.println("INF");
			else
				System.out.println(dist[i]);
		}

		scan.close();
	}

	public static void printMap() {
		System.out.println();
		for (int i = 1; i <= nV; i++) {
			for (int j = 1; j <= nV; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

bupjae 7년 전 0

V가 20000에 가까울 때 45번째 줄에서 필요한 메모리는 약 20000 * 20000 * 4 byte로, 약 1.6GB의 메모리를 요구하고 있습니다.

그래프를 저장할 수 있는 다른 데이터 구조를 사용하셔야 됩니다.

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

문제

문제

출처

ICPC

[Java] RunTime 오류 발생

javabank123 7년 전 0

bupjae 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말