글 읽기 - 메모리초과 문제 ㅠㅠ

dong1728 5년 전 0

어느 부분에서 메모리 초과가 나는지 모르겠습니다 ㅠ 테스트케이스가 별로 없어서 확인이힘드네요 ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static int n, m;
	static ArrayList<Integer> trustList[];
	static int childNum[];	
	static int maxChild = 0;
	static int visit[][];

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		trustList = new ArrayList[n+1];
		childNum = new int[n+1];
		for(int i = 0; i < trustList.length; ++i){
			trustList[i] = new ArrayList<Integer>();
		}
		
		for(int i = 0; i < m; ++i){
			st = new StringTokenizer(br.readLine());
			int rec = Integer.parseInt(st.nextToken());
			int sen = Integer.parseInt(st.nextToken());
			
			trustList[sen].add(rec);
			
		}
		visit = new int[n+1][n+1];
		int maxNum = dfs(1);
		LinkedList<Integer> niceHacking = new LinkedList<Integer>();
		niceHacking.add(1);
		if(n >= 2){
			for(int i = 2; i <= n; ++i){
				//System.out.println(dfs(i));
				visit = new int[n+1][n+1];
				int nowNum = dfs(i);
				if(nowNum > maxNum){
					niceHacking.clear();
					niceHacking.add(i);
				}else if(nowNum == maxNum){
					niceHacking.add(i);
				}
					
			}			
		}
		
		
		for(int i = 0; i < niceHacking.size(); ++i){
			System.out.print(niceHacking.get(i) + " ");
		}
		
		
		
		
		
		

	}
	
	static int dfs(int here){
		//visit[here][there] = 1;
		
		if(trustList[here].size() == 0){
			//childNum[start] = Math.max(childNum[start], cnt);
			
			
			return 0;
		}
		
		if(childNum[here] != 0){
			
			return childNum[here];
		}
			
		
		for(int i = 0; i < trustList[here].size(); ++i){
			if(visit[here][trustList[here].get(i)] != 1){
				visit[here][trustList[here].get(i)] = 1;
				childNum[here] += Math.max(childNum[here], dfs(trustList[here].get(i)) + 1);
			}
			
			//visit[here][trustList[here].get(i)] = 0;
			
			
		}
		
		
		
		return childNum[here];
		
	}

}

djm03178 5년 전 0

visit = new int[n+1][n+1];

은 C++ 기준으로 400MB의 메모리를 차지하고, 자바에서 사용하는 메모리는 이보다 더 많습니다.

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

문제

문제

출처

ICPC

메모리초과 문제 ㅠㅠ

dong1728 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말