글 읽기 - 1600 말이 되고픈 원숭이) 자바 메모리 초과뜨는 이유

leewwo2o 3년 전 0

메모리초과가 뜨는 이유를 모르겠습니다. 어디를 고치면 될까요? 그리고 말처럼 이동할때는 장애물(1)이 있는 위치에도 갈 수 있는건가요?

import java.util.*;
import java.io.*;

public class Main {
	static int n,w,h,ans=0; //ans는 시간계산용
	static int[][] map;
	static boolean[][][] vi;
	static int[] dx= {1,-1,0,0, -1,-2,-2,-1,1,2,2,1};
	static int[] dy= {0,0,1,-1, -2,-1,1,2,2,1,-1,-2};
	static Queue<xy> q=new LinkedList<>();
	static class xy{
		int x; //x좌표
		int y; //y좌표
		int kn; //k번 움직였는지 확인
		xy(int x,int y,int k){
			this.x=x;
			this.y=y;
			kn=k;
		}
	}
	static void bfs() {
		while(!q.isEmpty()) {
			int size=q.size();
			for(int k=0;k<size;k++) {
				xy nxy=q.poll();
				for(int i=0;i<4;i++) { //상하좌우만 먼저 계산
					int rx=nxy.x+dx[i];
					int ry=nxy.y+dy[i];
					if(rx<0||ry<0||rx>=h||ry>=w)
						continue;
					else if(vi[rx][ry][nxy.kn]==false&&map[rx][ry]==0) {
						boolean bb=true;
						for(int j=0;j<nxy.kn;j++) {
							if(vi[rx][ry][j]==true) {
								bb=false;
								break;
							}
						}
						if(bb==true) {
							if(rx==h-1&&ry==w-1) {
								ans++;
								return;
							}
							xy xxx=new xy(rx,ry,nxy.kn);
							q.offer(xxx);
							vi[rx][ry][nxy.kn]=true;
						}
					}
				}
				if(nxy.kn<n) { //k번 말과 같은 이동을 안했을시에만 확인
					for(int i=4;i<12;i++) {
						int rx=nxy.x+dx[i];
						int ry=nxy.y+dy[i];
						if(rx<0||ry<0||rx>=h||ry>=w)
							continue;
						else if(vi[rx][ry][nxy.kn]==false&&map[rx][ry]==0) {
							boolean bb=true;
							for(int j=0;j<nxy.kn;j++) {
								if(vi[rx][ry][j]==true) {
									bb=false;
									break;
								}
							}
							if(bb==true) {
								if(rx==h-1&&ry==w-1) {
									ans++;
									return;
								}
								xy xxx=new xy(rx,ry,nxy.kn+1);
								q.offer(xxx);
								vi[rx][ry][nxy.kn+1]=true;
							}
						}
					}
				}
			}
			ans++;
		}
		ans=-1;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		w=Integer.parseInt(st.nextToken());
		h=Integer.parseInt(st.nextToken());
		map=new int[h][w];
		vi=new boolean[h][w][n+1];
		for(int i=0;i<h;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<w;j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		xy d=new xy(0,0,0);
		q.offer(d);
		vi[0][0][0]=true;
		if(h==1&&w==1)
			bw.write(ans+"\n");
		else {
			bfs();
			bw.write(ans+"\n");
		}
		bw.flush();
		bw.close();
	}
}

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

문제

문제

출처

ICPC

1600 말이 되고픈 원숭이) 자바 메모리 초과뜨는 이유

leewwo2o 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말