글 읽기 - [Java]메모리 초과 오류

doryeongpark 5년 전 0

질문 포함 케이스는 다 맞고

해쉬맵으로 인접리스트를 구현하여 풀었습니다.

메모리 초과 오류가 났는데

코드 상에 수정해야될 부분이나 조언해주실 부분 있으면 답변 부탁드리겠습니다.

감사합니다.

import java.util.*;

public class Main {
	
	public static HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<Integer, ArrayList<Integer>>();
	public static HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
	public static LinkedList<Integer> queue = new LinkedList<Integer>();
	
	public static int target1;
	public static int target2;
	
	public static int result = 0;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int numOfPeople = sc.nextInt();
		for(int i = 1; i <= numOfPeople; ++i){
			adjList.put(i, new ArrayList<Integer>());
			visited.put(i, false);
		}
		
		target1 = sc.nextInt();
		target2 = sc.nextInt();
		
		if(target1 == target2){ System.out.println(0); return; }
		
		int numOfVertex = sc.nextInt();
		for(int i = 0; i < numOfVertex; ++i){
			int edge1 = sc.nextInt();
			int edge2 = sc.nextInt();
			adjList.get(edge1).add(edge2);
			adjList.get(edge2).add(edge1);
		}
		
		visited.put(target1, true);
		queue.addFirst(target1);
		bfs();
		
		System.out.println(result);

	}
	
	public static void bfs(){
		if(queue.isEmpty()){ result = -1; return; }
		int qSize = queue.size();
		for(int i = 0; i < qSize; ++i){
			int edge = queue.getLast();
			ArrayList<Integer> toList = adjList.get(edge);
			for(int j = 0; j < toList.size(); ++j){
				int nextEdge = toList.get(j);
				if(visited.get(nextEdge)){continue;}
				if(nextEdge == target2){
					++result;
					return;
				}
				queue.addFirst(nextEdge);
				visited.put(nextEdge, false);
			}
			queue.removeLast();
		}
		++result;
		bfs();
	}
	
}

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

문제

문제

출처

ICPC

[Java]메모리 초과 오류

doryeongpark 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말