[백준] 1600 : 말이 되고픈 원숭이 -JAVA(자바) - 사좋배 공유

 

 

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

public class Main_말이되고픈원숭이 {

	static int[][]arr;
	static int K;
	static int garo;
	static int sero;
	static Queue q;
	static int dx[]= {-1,0,1,0,-2,-1,1,2,2,1,-1,-2};
	static int dy[] = {0,1,0,-1,1,2,2,1,-1,-2,-2,-1};
	static boolean visit[][][];
	static int result;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		K = sc.nextInt();
		garo = sc.nextInt();
		sero = sc.nextInt();
		arr = new int[sero][garo];
		visit = new boolean[sero][garo][K+1];
		q= new LinkedList();

		result=0;
		//입력
		for(int i=0;i<sero;i++) {
			for(int j=0;j<garo;j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		q.add(new pos(0,0,0,0));
		for(int i=0;i<=K;i++) {
			visit[0][0][i]=true;
		}
		BFS();
		if(result==0) {
			System.out.println("-1");
			return;
		}
		System.out.println(result);
		
	}
	
	public static void BFS() {
		while(!q.isEmpty()) {
			pos temp = q.poll();
			int x = temp.x;
			int y= temp.y;
			int Kcount= temp.Kcount;
			int count =temp.count;
			//종료 조건
			if(x==sero-1&&y==garo-1) {
				result=count;
				q.clear();
				return;
			}
			
			for(int i=0;i<12;i++) {
				int rx = x+dx[i];
				int ry = y+dy[i];
				if(rx<0||ry<0||rx>=sero||ry>=garo||arr[rx][ry]==1) {
					continue;
				}
				if(i<4) {
					if(visit[rx][ry][Kcount]==false) {
						visit[rx][ry][Kcount]=true;
						q.add(new pos(rx,ry,Kcount,count+1));
					}
					
				}else{
					int nextCount=Kcount+1;
					if(nextCount<=K&&visit[rx][ry][nextCount]==false) {
						visit[rx][ry][nextCount]=true;
						q.add(new pos(rx,ry,nextCount,count+1));
					}
				}
			}
		}
	}
	private static class pos {
		int x;
		int y;
		int Kcount;
		int count;
		pos(int x, int y,int Kcount, int count){
			this.x = x;
			this.y= y;
			this.Kcount=Kcount;
			this.count=count;
		}
	}

}