백준 1600번: 말이 되고픈 원숭이

문제 설명

• https://www.acmicpc.net/problem/1600
• 원숭이가 (1,1)에서 (H,W)로 이동하는 가장 짧은 이동횟수를 구하는 문제입니다.
• 원숭이는 K번 말의 움직임으로 이동할 수 있습니다.
• 말의 움직임은 장애물(1)을 뛰어넘을 수 있습니다.

접근법

• k=1일 때 아래와 같은 입력이 주어졌다고 가정해 보겠습니다. (a의 값은 0입니다.)

0 0 0 0
0 0 a 0
0 0 1 1
0 0 1 0

a위치에 도달하는 방법은 두 가지 입니다.
첫째. 말의 움직임으로 한번에 (0,0)에서 a에 도달할 수 있습니다. -> 더 이상 말의 움직임으로 움직일 수 없기 때문에 (3,3)에 도달하지 못합니다.
둘째. 원숭이의 움직임으로 3번만에 (0,0)에서 a에 도달할 수 있습니다. -> 말의 움직임이 한번 남았기 때문에 1을 뛰어넘어 (3,3)에 도달할 수 있습니다.

이를 조금 더 확장시켜 생각해보면 board[i][j]에서 남은 말의 움직임이 몇 개냐에 따라 결과는 모두 달라집니다.

정답

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

class Main {
	static int[] M_dx = { 0, 1, 0, -1 };
	static int[] M_dy = { 1, 0, -1, 0 };
	static int[] H_dx = { -2, -2, -1, -1, 1, 1, 2, 2 };
	static int[] H_dy = { -1, 1, -2, 2, -2, 2, -1, 1 };
	static int r, c, k;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		k = sc.nextInt();
		c = sc.nextInt();
		r = sc.nextInt();
		int[][] board = new int[r][c];
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		System.out.println(BFS(board));
	}

	public static int BFS(int[][] board) {
		Queue<int[]> q = new LinkedList<int[]>();
		int[] start = { 0, 0, k };
		q.add(start);
		boolean[][][] v = new boolean[r][c][k+1];
		v[0][0][k] = true; 
		int cnt = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			cnt++;
			while (--size >= 0) {
				int[] now = q.poll();
				if (now[0] == (r - 1) && now[1] == (c - 1)) return cnt - 1;
				int jumpCnt = now[2];
				// 원숭이
				for (int d = 0; d < 4; d++) {
					int nx = now[0] + M_dx[d];
					int ny = now[1] + M_dy[d];
					if (0 <= nx && nx < r && 0 <= ny && ny < c && board[nx][ny] == 0 && !v[nx][ny][jumpCnt]) {
						v[nx][ny][jumpCnt] = true;
						int[] temp2 = { nx, ny, jumpCnt };
						q.add(temp2);
						
					}
				}
				// 말
				--jumpCnt;
				if (jumpCnt < 0) continue;
				for (int d = 0; d < 8; d++) {
					int nx = now[0] + H_dx[d];
					int ny = now[1] + H_dy[d];
					if (0 <= nx && nx < r && 0 <= ny && ny < c && board[nx][ny] == 0 && !v[nx][ny][jumpCnt]) {
						v[nx][ny][jumpCnt] = true;
						int[] temp2 = { nx, ny, jumpCnt };
						q.add(temp2);

					}
				}

			}
		}
		return -1;
	}

}

기타

• 이후 달이 차오른다, 가자.문제를 풀변서 3차원 방문처리를 완벽히 이해하는 걸 추천드립니다.