백준 1600번 말이 되고픈 원숭이 [ Java ]

1600번: 말이 되고픈 원숭이

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] dx = new int[]{0, 1, 2, 1, 2, 1, 0, -1, -2, -1, -2, -1};
        int[] dy = new int[]{1, 2, 1, 0, -1, -2, -1, -2, -1, 0, 1, 2};
        Queue<Monkey> Q = new LinkedList<>();
        int K = Integer.parseInt(br.readLine());
        String[] in = br.readLine().split(" ");
        int W = Integer.parseInt(in[0]);
        int H = Integer.parseInt(in[1]);
        int[][] field = new int[H][W];
        // 방문여부 + 말이동 사용 횟수
        boolean[][][] visited = new boolean[H][W][K+1];
        for (int i=0; i<H; i++)
            field[i] = Arrays.stream(br.readLine().split(" "))
                            .mapToInt(Integer::parseInt)
                            .toArray();

        Q.offer(new Monkey(0,0,0, K));
        while (!Q.isEmpty()){
            Monkey cur = Q.poll();
            if (cur.y==H-1 && cur.x==W-1){
                System.out.print(cur.dist);
                System.exit(0);
            }
            if (visited[cur.y][cur.x][cur.hpc]) continue;
            visited[cur.y][cur.x][cur.hpc] = true;

            for (int dir=0; dir<12; dir++){
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                if (nx<0 || nx>=W || ny<0 || ny>=H || field[ny][nx]==1) continue;

                // 일반이동
                if (dir%3==0)
                    Q.offer(new Monkey(nx, ny, cur.dist+1, cur.hpc));
                else if (cur.hpc>0) // 말이동이 가능하면
                    Q.offer(new Monkey(nx, ny, cur.dist+1, cur.hpc-1));
            }
        }
        System.out.print(-1);
    }
    static class Monkey{
        int x, y, dist, hpc; // horse power count
        public Monkey(int x, int y, int dist, int hpc){
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.hpc = hpc;
        }
    }
}