글 읽기 - 런타임 에러 원인을 잘 모르겠습니다.. ㅠㅠ 도와주세요

psh7341 7년 전 0

수행하면 채점을 조금 하다가 런타임 에러가 발생하는데요 원인을 잘 모르겠네요;;

도와주시면 감사하겠습니다 ㅠ

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int V;
	static int E;
	static int S;
	static Node[] nodes = new Node[20003];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(br.readLine().trim());
		
		for (int i = 1; i <= V; i++) {
			nodes[i] = new Node();
		}
		
		for (int i = 1; i <= E; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			nodes[s].neighbor[nodes[s].idx] = e;
			nodes[s].weight[nodes[s].idx++] = w;
		}
		
		Queue<Node> que = new LinkedList<>();
		
		que.add(nodes[S]);
		nodes[S].visited = true;
		nodes[S].cost = 0;
		
		while(!que.isEmpty()) {
			Node node = que.poll();
			
			int minVal = Integer.MAX_VALUE;
			int minIdx = -1;
			
			for (int i = 0; i < node.idx; i++) {
				nodes[node.neighbor[i]].cost = Math.min(nodes[node.neighbor[i]].cost, node.cost + node.weight[i]);
				if(nodes[node.neighbor[i]].cost < minVal && !nodes[node.neighbor[i]].visited) {
					minVal = nodes[node.neighbor[i]].cost;
					minIdx = node.neighbor[i];
				}
			}
			
			if(minIdx>0) {
				nodes[minIdx].visited = true;
				que.add(nodes[minIdx]);
			}
		}
		
		for (int i = 1; i <= V; i++) {
			if(nodes[i].cost == Integer.MAX_VALUE)
				System.out.println("INF");
			else
				System.out.println(nodes[i].cost);
		}
	}
	
	static class Node {
		int idx;
		boolean visited;
		int cost;
		int[] neighbor;
		int[] weight;
		
		public Node() {
			this.neighbor = new int[300003];
			this.weight = new int[300003];
			this.cost = Integer.MAX_VALUE;
		}
	}
}

leemk59 7년 전 0

메모리를 너무 많이 사용해서 그런 거 아닐까요?

Node 하나의 사이즈가 대략 2.4MB 이네요

(int 가 600,000 개 : 4 x 600,000 byte)

노드가 20,000 개라면 대략 40GB ... 라서 아마 out of memory 가 발생할 것 같습니다

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

문제

문제

출처

ICPC

런타임 에러 원인을 잘 모르겠습니다.. ㅠㅠ 도와주세요

psh7341 7년 전 0

leemk59 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말