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

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

문제 설명

H x W 격자에서 (0, 0) 에서 (H - 1, W - 1)로 가는 최소 동작 횟수를 구하는 문제이다. 각 칸에서 가능한 동작은 아래와 같다.

1. 상하좌우로 이동한다. 장애물이 존재하는 칸으로는 이동할 수 없다.
2. 체스의 나이트처럼 점프하여 이동한다. 장애물을 넘을 수 있고 장애물이 존재하는 칸으로는 이동할 수 없다. 단, 최대 K번까지만 체스처럼 점프할 수 있다.

문제 풀이

상하좌우와 나이트 처럼 이동하는 것은 dy dx 배열을 이용한다.
가중치가 동일한 최단거리 문제이므로 BFS를 이용하였다.
다만, 같은 행, 열이라도 점프를 횟수가 다르다면 다른 정점이어야 하므로 dist배열은 3차원 정수배열이다. (행, 열, 점프한 횟수)

사실 BFS이기 때문에(가중치가 동일하기 때문에) 3차원 정수 배열이 아니라 3차원 boolean배열을 사용하는 것이 더 알맞지 않을까 하는 생각도 들었으나 좀 더 일반적인 경우에도 적용가능한 이 형태로 구현했다.

3차원 boolean배열을 사용하는 경우,

1. Queue에 넣을 정점 정보에 동작 횟수를 추가하거나
2. Queue에서 꺼내기 전 Queue의 size를 저장해놓고, size만큼 꺼내고 인접 정점을 push하는 것을 반복하면 된다. 이렇게 하면 동일한 거리의 정점끼리 구분해서 꺼낼 수 있어 size를 저장하는 횟수가 곧 size만큼 꺼낼 정점들의 거리와 같아진다.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static Scanner sc = new Scanner(System.in);
	static StringTokenizer st;

	static int k, w, h, ans;
	static int[][] grid;
	static int[][][] dist;
	static int[] dy = { 0, 1, 0, -1 };
	static int[] dx = { 1, 0, -1, 0 };
	static int[] jdy = { 1, 2, 2, 1, -1, -2, -2, -1 };
	static int[] jdx = { 2, 1, -1, -2, -2, -1, 1, 2 };

	static class MyPoint extends Point {
		int jumpCnt;

		public MyPoint(int x, int y, int jumpCnt) {
			super(x, y);
			this.jumpCnt = jumpCnt;
		}
	}

	public static void main(String[] args) throws Exception {
		k = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		w = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());

		grid = new int[h][w];
		dist = new int[h][w][k + 1];

		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < w; j++) {
				grid[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		go();
		
		ans = Integer.MAX_VALUE;
		for (int i = 0; i <= k; i++) {
			int candidate = dist[h-1][w-1][i];
			
			// 방문하지 않은 곳은 -1
			if (candidate != -1) {
				ans = Math.min(ans, candidate);				
			}
		}
		
		System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
	}

	static void go() {
		Queue<MyPoint> queue = new ArrayDeque<>();

		// 초기화
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				Arrays.fill(dist[i][j], -1);
			}
		}
		dist[0][0][0] = 0;
		queue.add(new MyPoint(0, 0, 0));

		while (!queue.isEmpty()) {
			MyPoint cur = queue.poll();

			// jump를 안하는 경우
			for (int i = 0; i < 4; i++) {
				int nRow = cur.y + dy[i];
				int nCol = cur.x + dx[i];

				// 범위를 벗어나거나 이미 방문했거나 장애물이 있는 경우
				if (!inRange(nRow, nCol) || dist[nRow][nCol][cur.jumpCnt] != -1 || grid[nRow][nCol] == 1) {
					continue;
				}

				dist[nRow][nCol][cur.jumpCnt] = dist[cur.y][cur.x][cur.jumpCnt] + 1;
				queue.add(new MyPoint(nCol, nRow, cur.jumpCnt));
			}

			// 점프를 할 수 있어서 점프하는 경우
			if (cur.jumpCnt < k) {
				for (int i = 0; i < 8; i++) {
					int nRow = cur.y + jdy[i];
					int nCol = cur.x + jdx[i];

					// 범위를 벗어나거나 이미 방문했거나 장애물이 있는 경우
					if (!inRange(nRow, nCol) || dist[nRow][nCol][cur.jumpCnt + 1] != -1 || grid[nRow][nCol] == 1) {
						continue;
					}

					dist[nRow][nCol][cur.jumpCnt + 1] = dist[cur.y][cur.x][cur.jumpCnt] + 1;
					queue.add(new MyPoint(nCol, nRow, cur.jumpCnt + 1));
				}
			}
		}
	}

	static boolean inRange(int row, int col) {
		return 0 <= row && row < h && 0 <= col && col < w;
	}
}