[BOJ] 1600. 말이 되고픈 원숭이

문제 원본 : https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int k = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());

        String[][] map = new String[h][w];
        for (int i = 0; i < h; ++i) {
            map[i] = br.readLine().split(" ");
        }

        boolean[][][] v = new boolean[h][w][k + 1];
        int[][][] dist = new int[h][w][k + 1];
        int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(0, 0, 0));

        v[0][0][0] = true;
        while (!q.isEmpty()) {
            Pos p = q.poll();
            for (int i = 0; i < 12; ++i) {
                int ny = p.y + dir[i][0];
                int nx = p.x + dir[i][1];

                if (ny >= 0 && nx >= 0 && ny < h && nx < w && map[ny][nx].equals("0")) {
                    if (i < 4 && !v[ny][nx][p.knight]) {
                        q.add(new Pos(ny, nx, p.knight));
                        dist[ny][nx][p.knight] = dist[p.y][p.x][p.knight] + 1;
                        v[ny][nx][p.knight] = true;
                    } else if (i >= 4 && p.knight < k && !v[ny][nx][p.knight + 1]) {
                        q.add(new Pos(ny, nx, p.knight + 1));
                        dist[ny][nx][p.knight + 1] = dist[p.y][p.x][p.knight] + 1;
                        v[ny][nx][p.knight + 1] = true;
                    }
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        boolean isPossible = false;
        for (int i = 0; i <= k; ++i) {
            if (v[h - 1][w - 1][i]) {
                isPossible = true;
                ans = Math.min(ans, dist[h - 1][w - 1][i]);
            }
        }

        bw.write(isPossible ? Integer.toString(ans) : Integer.toString(-1));

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

    public static class Pos {
        public int y;
        public int x;
        public int knight;

        public Pos(int y, int x, int knight) {
            this.y = y;
            this.x = x;
            this.knight = knight;
        }
    }
}

• 2206. 벽 부수고 이동하기 문제와 유사한 문제이다.
• 다른 점은 벽 부수는 건 한 번까지만 되고 말처럼 이동하는 건 k번만큼 가능하다는 것뿐이다.
• 이제 이런 BFS 유형은 감을 잡은 것 같다.