BJ1600 말이 되고픈 원숭이

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

BFS를 사용해 구현하는 문제이다.
하지만 점프 횟수라는 조건 때문에 방문처리를 할 때, 점프 횟수에 따라 각각의 맵에 따로 처리를 해주어야 한다.

boolean visit 배열을 3차원으로 만들어 해결해주었다.

package day0330;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class WannabeMonkey {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int jump, W, H;
	static int[][] map;
	static boolean[][][] visit;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static int[] hx = { -2, -2, 2, 2, 1, -1, 1, -1 };
	static int[] hy = { 1, -1, 1, -1, 2, 2, -2, -2 };

	static class Monkey {
		int x;
		int y;
		int cnt;
		int k;

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

	private static void bfs() throws IOException {
		Queue<Monkey> q = new LinkedList<Monkey>();
		q.add(new Monkey(0, 0, 0, jump));

		while (!q.isEmpty()) {
			Monkey curMonkey = q.poll();
			int monkeyX = curMonkey.x;
			int monkeyY = curMonkey.y;
			int cnt = curMonkey.cnt;
			int monkeyJump = curMonkey.k;

			if (monkeyX == W - 1 && monkeyY == H - 1) {
				bw.append(cnt + "");
				return;
			}
			if (monkeyX >= W || monkeyY >= H || monkeyX < 0 || monkeyY < 0)
				continue;
			if (map[monkeyY][monkeyX] == 1)
				continue;

			if (visit[monkeyY][monkeyX][monkeyJump])
				continue;
			visit[monkeyY][monkeyX][monkeyJump] = true;

			for (int i = 0; i < 4; i++) {
				int nextX = monkeyX + dx[i];
				int nextY = monkeyY + dy[i];

				q.add(new Monkey(nextX, nextY, cnt + 1, monkeyJump));

			}

			if (monkeyJump != 0) {
				for (int i = 0; i < 8; i++) {
					int nextX = monkeyX + hx[i];
					int nextY = monkeyY + hy[i];

					q.add(new Monkey(nextX, nextY, cnt + 1, monkeyJump - 1));
				}
			}
		}
		bw.append("-1");
		return;

	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine(), " ");
		jump = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine(), " ");
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		map = new int[H][W];
		visit = new boolean[H][W][31];
		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());
			}
		}

		visit[0][0][0] = true;
		bfs();
		bw.flush();
	}
}