말이 되고픈 원숭이

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

풀이

원숭이는 말처럼 이동할 수도 있고 일반적인 원숭이처럼 이동할 수도 있다.

그래서 bfs를 할 때 두가지 경우로 나누어서 큐에 집어넣었다.

먼저 말처럼 이동이 가능한 경우

해당 위치로 이동이 가능하면 말처럼 이동 가능하게 해준다.

그리고 말처럼 이동 가능 여부에 상관없이 일반적으로 이동하는 경우에 대해서도 큐에 집어넣어야 한다.

처음에는 2차원 배열로 visit 체크를 했는데 이럴 경우 최적을 보장하지 못한다는 문제가 있다.

따라서 3차원 visit 배열에 해당 좌표에 도달하는데 말처럼 이동한 횟수(k)에 moveCnt를 저장하여 목적지에 도달했을 때 최소를 찾는 방법으로 구현했다.

코드

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int n, m, k;
    static int[][] map;
    static int[][][] visit;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[] hx = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int[] hy = {1, -1, 2, -2, 2, -2, 1, -1};

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        k = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        m = Integer.parseInt(input[0]);
        n = Integer.parseInt(input[1]);

        map = new int[n][m];
        visit = new int[n][m][k + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int t = 0; t <= k; t++)
                    visit[i][j][t] = Integer.MAX_VALUE;
            }
        }

        String[] line;
        for (int i = 0; i < n; i++) {
            line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(line[j]);
            }
        }
        bfs();

        int min = Arrays.stream(visit[n - 1][m - 1]).min().getAsInt();
        if (min == Integer.MAX_VALUE)
            bw.write("-1\n");
        else
            bw.write(min + "\n");

        bw.close();
        br.close();
    }

    private static void bfs() {
        Pair monkey = new Pair(0, 0, 0, 0);
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(monkey);

        for (int i = 0; i <= k; i++)
            visit[0][0][i] = 0;

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
;
            if (p.kCnt < k) {
                for (int i = 0; i < 8; i++) {
                    int nx = p.x + hx[i];
                    int ny = p.y + hy[i];
                    int c = p.kCnt;
                    if ((nx >= 0 && nx < n) && (ny >= 0 && ny < m) && map[nx][ny] == 0) {
                        if (p.moveCnt + 1 < visit[nx][ny][c + 1]) {
                            visit[nx][ny][c + 1] = p.moveCnt + 1;
                            queue.offer(new Pair(nx, ny, c + 1, p.moveCnt + 1));
                        }
                    }
                }
            }

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                int c = p.kCnt;
                if ((nx >= 0 && nx < n) && (ny >= 0 && ny < m) && map[nx][ny] == 0) {
                    if (p.moveCnt + 1 < visit[nx][ny][c]) {
                        visit[nx][ny][c] = p.moveCnt + 1;
                        queue.offer(new Pair(nx, ny, c, p.moveCnt + 1));
                    }
                }
            }
        }
    }
}

class Pair {
    int x;
    int y;
    int kCnt;
    int moveCnt;

    public Pair(int x, int y, int kCnt, int moveCnt) {
        this.x = x;
        this.y = y;
        this.kCnt = kCnt;
        this.moveCnt = moveCnt;
    }

    @Override
    public String toString() {
        return "Pair{" +
                "x=" + x +
                ", y=" + y +
                ", kCnt=" + kCnt +
                ", moveCnt=" + moveCnt +
                '}';
    }
}