글 읽기 - 정답은 잘 나오나, 제출 시 런타임에러 때문에 글 올려요

geulrara123 7년 전 1

여러 테스트 케이스로 돌려보니,

답은 잘 나오는데...문제는 백준에서의 런타임 에러네요

고수님들 도와주세요ㅠㅠ

import java.util.PriorityQueue;
import java.util.Scanner;

class Element implements Comparable<Element> {
	private int index;
	private int distance;

	Element(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}

	public int getIndex() {
		return index;
	}

	public int getDistance() {
		return distance;
	}

	@Override
	public int compareTo(Element o) {
		// TODO Auto-generated method stub
		return 0;
	}

}

public class Main {

	static int v, e;
	static int start;
	static int[][] arr;
	static int[] dist;
	static PriorityQueue<Element> pq = new PriorityQueue<Element>();
	static final int INF = 10001;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		v = sc.nextInt();
		e = sc.nextInt();
		start = sc.nextInt();
		arr = new int[v + 1][v + 1];
		dist = new int[v + 1];

		for (int i = 1; i <= e; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();

			arr[a][b] = c;
		}

		for (int i = 1; i <= v; i++) {
			dist[i] = INF;
		}
		dist[start] = 0;

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

	}

	public static void ssp(int start) {
		pq.offer(new Element(start, dist[start]));

		while (!pq.isEmpty()) {
			int cost = pq.peek().getDistance();
			int index = pq.peek().getIndex();
			pq.poll();

			for (int i = 1; i <= v; i++) {
				if (arr[index][i] != 0 && dist[i] > dist[index] + arr[index][i]) {
					dist[i] = dist[index] + arr[index][i];
					pq.offer(new Element(i, dist[i]));
				}
			}
		}
	}

}

yukariko 7년 전 1

정점의 범위가 2만인데, 2만 * 2만의 배열을 생성하게되면 메모리초과가 발생할 수 있습니다.

BOJ에서는 너무 심한 메모리초과는 런타임에러로 표시될 수 있습니다.

geulrara123 7년 전 0

아..메모리초과 문제였군요..감사합니다.

죄송하지만, 하나만 더 여쭙겠습니다.

다른 분들 코드를 보니 대부분 배열안에 List형태의 객체를 넣어서 구현했드라구요..

근데, 저는 저렇게 이차원배열로 꼭 구현을 해보고 싶은데, 이럴 경우에 어떻게 고치면 될까요?..

yukariko 7년 전 0

방법은 여러가지가 있겠지만, 제 생각엔 입력을 다 한곳에 모은다음, 각 정점마다 엣지가 몇개인지를 카운팅하여 정점마다 크기를 다르게 2차원배열을 선언하여 사용하면 될 것 같습니다.

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

문제

문제

출처

ICPC

정답은 잘 나오나, 제출 시 런타임에러 때문에 글 올려요

geulrara123 7년 전 1

yukariko 7년 전 1

geulrara123 7년 전 0

yukariko 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말