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

문제 출처: www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

: 원숭이에게 말처럼 움직일 수 있는 횟수가 주어지고 말처럼 이동하거나 인접한 칸으로 이동하여 가장 왼쪽 상단에서 가장 우측 하단으로 이동할 때 소요되는 원숭이의 최소 동작수를 구해야 한다.

: 원숭이에게 주어진 횟수가 달라질 때마다 그리고, 원숭이가 말처럼 행동하거나 행동하지 않을 때마다 다른 갈래로 움직여야 하기 때문에 이를 저장할 수 있도록 visited 배열을 3차원으로 만든다.

: 말처럼 행동할 때마다 말처럼 행동 가능한 횟수를 줄이고 그에 해당하는 visited배열에 표시할 수 있도록 한다.

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 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static class Status{
		int x, y, len, cnt; // x좌표, y좌표, 동작 횟수, 말처럼 움직일 수 있는 횟수

		public Status(int x, int y, int len, int cnt) {
			super();
			this.x = x;
			this.y = y;
			this.len = len;
			this.cnt = cnt;
		}

		@Override
		public String toString() {
			return "Status [x=" + x + ", y=" + y + ", len=" + len + ", cnt=" + cnt + "]";
		}
		
	}
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static int[] horseR = {-2, -1, 1, 2, 2, 1, -1, -2};
	static int[] horseC = {1, 2, 2, 1, -1, -2, -2, -1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		int K = Integer.parseInt(br.readLine()); // K번 말처럼 움직일 수 있음
		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N][M];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int ans = 0;
		boolean[][][] v = new boolean[N][M][K+1];
		Queue<Status> q = new LinkedList<>();
		q.add(new Status(0,0,0,K));
		
		while(!q.isEmpty()) {
			Status cur = q.poll();
			if(cur.x == N-1 && cur.y == M-1) {
				ans = cur.len;
				break;
			}
			// 원숭이처럼 움직이는 경우
			for(int d = 0; d < 4; d++) {
				int nr = cur.x + dr[d];
				int nc = cur.y + dc[d];
				if(nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc] == 1 || v[nr][nc][cur.cnt]) continue;
				v[nr][nc][cur.cnt] = true;
				q.add(new Status(nr, nc, cur.len+1, cur.cnt));
			}
			// 말처럼 움직일 수 있는 경우
			if(cur.cnt > 0) {
				for(int d = 0; d < 8; d++) {
					int nr = cur.x + horseR[d];
					int nc = cur.y + horseC[d];
					if(nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc] == 1 || v[nr][nc][cur.cnt-1]) continue;		
					v[nr][nc][cur.cnt-1] = true;
					q.add(new Status(nr, nc, cur.len+1, cur.cnt-1));
				}				
			}
		}
		if(N==1 && M == 1)System.out.println(0);
		else if(ans == 0) System.out.println("-1");
		else System.out.println(ans);
		
	}
}