[백준] 말이 되고픈 원숭이 1600 - JAVA

문제

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

코드

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

class Main{	
	static int k, w, h;
	static int board[][];
	static int visited[][][];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		k = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		
		w = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		
		board = new int [h][w];
		visited = new int [h][w][32];
		
		for(int i=0;i<h;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<w;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		bfs();
		
		int min = 50000;
		for(int i=0;i<=k;i++) {
			if(visited[h-1][w-1][i] > 0) {
			
				if(min > visited[h-1][w-1][i]) {
					min = visited[h-1][w-1][i];
				}
			}
		}
		
		if(min == 50000)
			System.out.print(-1);
		else
			System.out.print(min-1);
	}

	
	static void bfs() {
		
		int dx [] = {0, 1, 0, -1};
		int dy [] = {1, 0, -1, 0};
		
		int hdx [] = {2, 2, 1, 1, -1, -1, -2, -2};
		int hdy [] = {1, -1, 2, -2, 2, -2, 1, -1};
		
		Queue<Point> que = new LinkedList<>();
			
		que.add(new Point(0, 0, 0));
		visited[0][0][0] = 1;
		
		while(!que.isEmpty()) {
			Point cur = que.poll();
			int x = cur.x;
			int y = cur.y;
			int cnt = cur.cnt;
			
			if(cnt < k) {
				for(int i=0;i<8;i++) {
					int nx = x + hdx[i];
					int ny = y + hdy[i];
					
					if(range(nx, ny) || board[nx][ny] == 1) continue;
					if(visited[nx][ny][cnt+1] != 0) continue;
					
					que.add(new Point(nx, ny, cnt+1));
					visited[nx][ny][cnt+1] = visited[x][y][cnt]+1;
				}
			}
			for(int i=0;i<4;i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(range(nx, ny) || board[nx][ny] == 1) continue;
				if(visited[nx][ny][cnt] != 0) continue;
				
				que.add(new Point(nx, ny, cnt));
				visited[nx][ny][cnt] = visited[x][y][cnt]+1;
			}
			
		}
		
		
		
		
	}
	
	static boolean range(int x, int y) {
		return x < 0 || y < 0 || x >= h || y >=w;
	}
	
	static class Point {
		int x;
		int y;
		int cnt;
		
		Point(int x, int y, int cnt){
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
}