[백준] 1600번 말이 되고픈 원숭이 (java, bfs)

vis배열을 3차원으로 해줘야되는지 모르고 풀었다가,, 결국 풀었다 ㅠㅠ 인간승리 흑흑

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Monkey{
	int x;
	int y;
	int cnt;
	int k;
	public Monkey(int x, int y,int cnt,int k) {
		this.x = x;
		this.y = y;
		this.cnt=cnt;
		this.k = k;
	}
	
}

public class B_1600_말이되고픈원숭이_Main {
	static int k,w,h;
	static int[][] map;
	static int xpos[]= {0,0,1,-1, 1, 2,2,1,-1,-2,-2,-1};//인덱스3까지 기본 이동
	static int ypos[]= {1,-1,0,0,-2,-1,1,2, 2, 1,-1,-2};
	static boolean[][][] vis;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		k=sc.nextInt();
		w=sc.nextInt();
		h=sc.nextInt();
		map=new int[h][w];
		vis=new boolean[h][w][k+1];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				map[i][j]=sc.nextInt();
			} 
		}

		Queue<Monkey> q=new LinkedList<Monkey>();
		q.add(new Monkey(0,0,0,k));
		vis[0][0][0]=true;
		while(q.size()!=0) {
			Monkey cur=q.poll();
			int x=cur.x;
			int y=cur.y;
			int cnt=cur.cnt;// 이동 횟수
			int left=cur.k;
			if(x==w-1 && y==h-1) {
				System.out.println(cnt);
				return;
			}

			for (int i = 0; i < 12; i++) {
				if(i==4 && left==0)break;
				int yy=y+ypos[i];
				int xx=x+xpos[i];
				if(xx<0 || yy<0 || xx>=w || yy>=h)continue;
				if(map[yy][xx]==1)continue;
				if(i<4) {
					if(vis[yy][xx][left])continue;
					vis[yy][xx][left]=true;
					q.add(new Monkey(xx,yy,cnt+1,left));
				}else {
					if(vis[yy][xx][left-1])continue;
					vis[yy][xx][left-1]=true;
					q.add(new Monkey(xx,yy,cnt+1,left-1));
				}	
			}
		}
		System.out.println(-1);
		
		
	}
}