글 읽기 - 메모리초과가 나는 이유가 무엇일까요?[공지사항읽음]

doryeongpark 5년 전 0

재귀로 포인트 두개를 선택한 뒤 그때그떄 bfs를 사용하고 그중에서 최대값을 구하는 방법을 사용했습니다.

개선해야될 점 있으면 답변 부탁드립니다.

import java.util.*;

public class Main {
	
	public static class Position{
		int x; int y;
		public Position(int x, int y){
			this.x = x; this.y = y;
		}
		public boolean equals(int x, int y){
			return this.x == x && this.y == y;
		}
		public boolean equals(Position another){
			return this.x == another.x && this.y == another.y;
		}
		public String toString(){
			return "[" + x + ", " + y + "]";
		}
	}

	public static int col;
	public static int row;
	
	public static char[][] field;
	public static boolean[][] visited;
	public static LinkedList<Position> queue = new LinkedList<Position>();
	public static LinkedList<Position> picked = new LinkedList<Position>();
	
	public static int[] offsetX = {0, 0, -1, 1};
	public static int[] offsetY = {1, -1, 0, 0};
	
	public static int counter = 0;
	public static Vector<Integer> counters = new Vector<Integer>();
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		col = sc.nextInt();
		row = sc.nextInt();
		
		field = new char[col][row];
		visited = new boolean[col][row];
		
		sc.nextLine();
		for(int y = 0; y < col; ++y){
			String line = sc.nextLine();
			for(int x = 0; x < row; ++x){
				field[y][x] = line.charAt(x);
			}
		}
		setTargetLocation(2, picked);
		
		if(counters.size() == 0){System.out.println(0); return;}
		int max = Integer.MIN_VALUE;
		for(int result : counters){
			if(result > max){max = result;}
		}
		System.out.println(max);
	}
	
	//Brute Force
	public static void setTargetLocation(int depth, LinkedList<Position> picked){
		
		if(depth == 0){
			Position target1 = picked.get(0);
			Position target2 = picked.get(1);
			if(target1.equals(target2)){return;}
			resetVisited();
			queue.clear();
			queue.addFirst(target1);
			visited[target1.y][target1.x] = true;
			bfs(target2);
			return;
		}
		
		for(int y = 0; y < col; ++y){
			for(int x = 0; x < row; ++x){
				char val = field[y][x];
				if(val == 'W'){continue;}
				picked.addFirst(new Position(x, y));
				setTargetLocation(depth - 1, picked);
				picked.removeFirst();
			}
		}
	}
	
	public static void bfs(Position dest){
		
		if(queue.isEmpty()){
			counter = 0;
			return;
		}
		++counter;
		int qSize = queue.size();
		for(int i = 0; i < qSize; ++i){
			Position pos = queue.getLast();
			for(int j = 0; j < offsetX.length; ++j){
				int newX = pos.x + offsetX[j];
				int newY = pos.y + offsetY[j];
				if(newX < 0 || newX >= row){continue;}
				if(newY < 0 || newY >= col){continue;}
				if(field[newY][newX] == 'W'){continue;}
				if(visited[newY][newX]){continue;}
				if(dest.equals(newX, newY))
				{
					counters.add(counter);
					counter = 0;
					return;
				}
				queue.addFirst(new Position(newX, newY));
				visited[newY][newX] = true;	
			}
			queue.removeLast();
		}
		
		bfs(dest);
	}
	
	public static void resetVisited(){
		
		for(int y = 0; y < col; ++y){
			for(int x = 0; x < row; ++x){
				visited[y][x] = false;
			}
		}
		
	}
	
}

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

문제

문제

출처

ICPC

메모리초과가 나는 이유가 무엇일까요?[공지사항읽음]

doryeongpark 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말