글 읽기 - 런타임 에러가 계속 생겨요 도와주세요 ㅠ

cheon406 7년 전 0

오늘 계속 런타임 에러가 생겨요 ㅠㅠㅠㅠㅠ

어디서 왜 나는 걸까요ㅠㅠㅠㅠㅠㅠ도와주세요

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	static int N, M;
	static int arr[][];
	static boolean visited[][];
	static int res[];
	static int ans = 0;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		arr = new int[N + 1][N + 1];
		visited = new boolean[N + 1][N + 1];
		res = new int[N + 1];
		
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			arr[b][a] = 1;
		}
		
		for (int i = 1; i <= N; i++) {
			dfs(i, i);
			if (ans < res[i]) {
				ans = res[i];
			}
		}
		
		for (int i = 1; i <= N; i++) {
			if (res[i] == ans) {
				System.out.print(i + " ");
			}
		}
	}
	
	static void dfs(int first, int num) {
		for (int j = 1; j <= N; j++) {
			if (arr[num][j] == 1 && visited[j][first] == false) {
				res[first]++;
				visited[j][first] = true;
				dfs(first, j);
			}
		}
	}
}

zlzmsrhak 7년 전 0

arr의 배열 크기를 계산해보면 4byte * 10000 * 10000으로 거의 4GB에 가깝게 나옵니다.

이 정도로 큰 배열의 경우 런타임 에러가 날 수도 있습니다.

cheon406 7년 전 0

@zlzmsrhak 그럼 어떻게 하면 좋을까요? 배열대신 벡터를 써야할까요? 팁을 좀 주시면 안될까요..

zlzmsrhak 7년 전 0

그래프를 표현할 때 ArrayList 배열을 정의한 후, i번째 ArrayList에는 i번 정점과 인접한 정점들 번호들을 저장하는 방식을 사용하는것이 좋습니다.

정확히 간선 개수만큼의 메모리를 사용하기 때문에 그래프를 표현하는 데 문제가 되지 않습니다.

visit 배열도 i번 정점을 확인한 후 전부 0으로 초기화를 해 주는 방식으로 크기를 줄일 수 있습니다.

cheon406 7년 전 0

@zlzmsrhak 도움이 많이 되었어요. 감사합니다!

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

문제

문제

출처

ICPC

런타임 에러가 계속 생겨요 도와주세요 ㅠ_ㅠ

cheon406 7년 전 0

zlzmsrhak 7년 전 0

cheon406 7년 전 0

zlzmsrhak 7년 전 0

cheon406 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말