글 읽기 - 런타임 에러 (ArrayIndexOutOfBounds) 어디서 나는걸까요? ㅠㅠ

hoyoung205 3년 전 0

런타임 에러 (ArrayIndexOutOfBounds) 가 계속 발생하네요.

배열이랑 인접리스트 N+2 까지만 선언했는데.. 어떨때 array index 를 벗어나는걸까요?

답변 부탁드립니다.

//package P_13_3;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// [골드2] 소수마을
public class Main {

	static ArrayList<Edge> adjList[];
	static int max = 8000;
	static boolean prime[];
	static int X1, Y1, X2, Y2, N;
	static long ans;
	static int dist[];
	static ArrayList<Node> nodeList;

	static class Edge implements Comparable<Edge> {
		int idx;
		int v;

		public Edge(int idx, int v) {
			this.idx = idx;
			this.v = v;
		}

		@Override
		public int compareTo(Edge o) {
			return this.v - o.v;
		}
	}

	static class Node {
		int a;
		int b;

		public Node(int a, int b) {
			this.a = a;
			this.b = b;
		}

//		@Override
//		public int compareTo(Node o) {
//			return Long.compare(this.v, o.v);
//		}
	}

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("src\\P_13_3\\B_14431.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// int T = Integer.parseInt(br.readLine());

		// for (int tc = 1; tc <= T; tc++) {
		StringTokenizer st = new StringTokenizer(br.readLine());
		X1 = Integer.parseInt(st.nextToken());
		Y1 = Integer.parseInt(st.nextToken());
		X2 = Integer.parseInt(st.nextToken());
		Y2 = Integer.parseInt(st.nextToken());

		N = Integer.parseInt(br.readLine());

		prime = new boolean[max+1];
		nodeList = new ArrayList<Node>();

		setPrime();
		prime[0] = true;
		prime[1] = true;

		nodeList.add(new Node(X1, Y1));
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			nodeList.add(new Node(a, b));
		}
		nodeList.add(new Node(X2, Y2));

		dist = new int[N + 2];
		adjList = new ArrayList[N + 2];
		for (int i = 0; i < N + 2; i++) {
			adjList[i] = new ArrayList<Edge>();
			dist[i] = Integer.MAX_VALUE;
		}

		for (int i = 0; i < N + 2; i++) {
			for (int j = 0; j < N + 2; j++) {
				
				if (i == j) {
					continue;
				}
				
				//System.out.println(i + " " + j);

				int a1 = nodeList.get(i).a;
				int b1 = nodeList.get(i).b;

				int a2 = nodeList.get(j).a;
				int b2 = nodeList.get(j).b;

				// System.out.println(a1 + " " + b1 + " " + a2 + " " + b2);

				int v = (int) Math.sqrt((a1 - a2) * (a1 - a2) + (b1 - b2) * (b1 - b2));
				// System.out.println(v);

//				if (!prime[v]) {
				adjList[i].add(new Edge(j, v));
				//adjList[j].add(new Edge(i, v));
//				}

			}

		}

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		dist[0] = 0;
		pq.add(new Edge(0, 0));

		while (!pq.isEmpty()) {
			Edge nowE = pq.poll();
//			if (nowNode.v > dist[nowNode.idx]) {
//				continue;
//			}
			for (Edge nextE : adjList[nowE.idx]) {
				// System.out.println(nextE.v);
				//
				if (!prime[nextE.v] && dist[nextE.idx] > dist[nowE.idx] + nextE.v) {
					dist[nextE.idx] = dist[nowE.idx] + nextE.v;
					pq.add(new Edge(nextE.idx, dist[nextE.idx]));
				}
			}
		}

//		for (int i = 1; i <= N + 2; i++) {
//			System.out.println(dist[i]);
//		}

		if (dist[N + 1] == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(dist[N + 1]);
		}

	}

	private static void setPrime() {
		int sqrt = (int) Math.sqrt(max);
		for (int i = 2; i < sqrt; i++) {
			if (prime[i]) {
				continue;
			}
			for (int j = i + i; j <= max; j += i) {
				prime[j] = true;
			}
		}

	}

}

hoyoung205 3년 전 0

!prime[nextE.v] <-- 소수 판단을 인접리스트 구할시로 이동하니, 컴파일 에러는 사라지네요.

테스트 케이스 중에 먼저 체크하고 인접리스트 구성이랑 최소 간선 비교시에 소수 판별하는거랑 차이가 있는걸까요?

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

문제

문제

출처

ICPC

런타임 에러 (ArrayIndexOutOfBounds) 어디서 나는걸까요? ㅠㅠ

hoyoung205 3년 전 0

hoyoung205 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말