[BOJ 1600] 말이 되고픈 원숭이 (Java)

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

1600번: 말이 되고픈 원숭이

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

public class Main_BOJ_1600 {
	static class Monkey{
		int r, c, K, dist;
		public Monkey(int r, int c, int K, int dist) {
			this.r=r;
			this.c=c;
			this.K=K;
			this.dist=dist;
		}
	}
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int[] hr={-2,-2,2,2,1,-1,1,-1};
	static int[] hc={1,-1,1,-1,2,2,-2,-2};
	static int K;
	static int W, H;
	static int[][] map;
	static boolean[][][] check;
	static int answer=-1;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		K=Integer.parseInt(br.readLine());
		StringTokenizer st=new StringTokenizer(br.readLine());
		W=Integer.parseInt(st.nextToken());
		H=Integer.parseInt(st.nextToken());
		map=new int[H][W];
		check=new boolean[H][W][K+1];
		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());
			}
		}
		bfs();
		System.out.println(answer);
	}
	private static void bfs() {
		Queue<Monkey> q=new LinkedList<>();
		q.add(new Monkey(0,0,0,0));
		check[0][0][0]=true;
		while (!q.isEmpty()) {
			Monkey curr=q.poll();
			if (curr.r==(H-1) && curr.c==(W-1)) {
				answer=curr.dist;
				break;
			}
			for (int i=0; i<4; i++) {
				int nr=curr.r+dr[i];
				int nc=curr.c+dc[i];
				if (nr<0 || nc<0 || nr>=H || nc>=W) continue;
				if (map[nr][nc]==0 && !check[nr][nc][curr.K]) {
					check[nr][nc][curr.K]=true;
					q.add(new Monkey(nr, nc, curr.K, curr.dist+1));
				}
			}
			if (curr.K>=K) continue;
			for (int i=0; i<8; i++) {
				int nr=curr.r+hr[i];
				int nc=curr.c+hc[i];
				if (nr<0 || nc<0 || nr>=H || nc>=W) continue;
				if (map[nr][nc]==0 && !check[nr][nc][curr.K+1]) {
					check[nr][nc][curr.K+1]=true;
					q.add(new Monkey(nr, nc, curr.K+1, curr.dist+1));
				}
			}
		}
		
	}

}

3차원 visited 배열을 사용해서 푸는 문제.

여기서 check[r][c][k] 는 k번의 능력을 사용해서 r,c 에 도착했는지 여부를 나타낸다. 각 k에 따라 경로가 달라진다.

BFS 에서 탐색할 때마다, 인접 4방향+인접 말의 8방향을 탐색한다(능력이 남아있는 경우에)

이때 큐에 넣는 기준은 장애물이 없고, 인접 말 8방향의 경우 check[r][c][curr.k+1] 가 false 일 때이다.