문제해설

이전에 풀었던 2206번 벽 부수고 이동하기 문제와 풀이 방법이 완전 똑같다. (이해를 돕기위해 한번 읽어보고 오는것을 추천합니다.)
조금 다른점이 있다면 한번에 나이트 처럼 움직일 수 있는 이동 방법과 나이트처럼 이동 할 수 있는 횟수가 1번이 아닌 K번으로 주어지는 것이다. 이 문제 역시 기본적인 BFS문제에서 방문처리만 나이트처럼 몇번 움직였는지에 따라 각각 체크해줘야한다.
따라서 방문체크 배열을 visit[H][W][K]로 선언하고 넓이 우선 탐색으로 최소값을 찾으면 된다.

BFS, Graph

시간복잡도

최악의 경우 H * W 크기의 맵을 K 번 탐색해야하므로 O(H * W * K)이다. (H, W <= 200, K <= 30)

코드

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

public class Main {
    static int K, W, H, map[][];
    static int monkey_row[] = {0, 0, 1, -1}, monkey_col[] = {1, -1, 0, 0};
    static int horse_row[] = {1, 1, -1, -1, 2, 2, -2, -2}, horse_col[] = {2, -2, 2, -2, 1, -1, 1, -1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        K = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        map = new int[H][W];
        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());
            }
        }
        if (H == 1 && W == 1) bw.write("0");
        else bw.write(String.valueOf(bfs()));
        bw.flush();
        bw.close();
    }

    static int bfs() {
        Queue<node_1600> queue = new LinkedList<>();
        boolean visit[][][] = new boolean[H][W][K + 1];
        queue.offer(new node_1600(0, 0, K, 0));
        visit[0][0][K] = true;

        while (!queue.isEmpty()) {
            node_1600 n = queue.poll();

            for (int i = 0; i < 4; i++) {
                int r = n.row + monkey_row[i], c = n.col + monkey_col[i];
                if (r < 0 || c < 0 || H <= r || W <= c || map[r][c] == 1 || visit[r][c][n.horse]) continue;
                if (r == H - 1 && c == W - 1) return n.count + 1;
                queue.offer(new node_1600(r, c, n.horse, n.count + 1));
                visit[r][c][n.horse] = true;
            }
            if (n.horse == 0) continue;
            for (int i = 0; i < 8; i++) {
                int r = n.row + horse_row[i], c = n.col + horse_col[i];
                if (r < 0 || c < 0 || H <= r || W <= c || map[r][c] == 1 || visit[r][c][n.horse - 1]) continue;
                if (r == H - 1 && c == W - 1) return n.count + 1;
                queue.offer(new node_1600(r, c, n.horse - 1, n.count + 1));
                visit[r][c][n.horse - 1] = true;
            }
        }
        return -1;
    }
}

class node_1600 {
    int row, col, horse, count;
    node_1600(int row, int col, int horse, int count) {
        this.row = row;
        this.col = col;
        this.horse = horse;
        this.count = count;
    }
}