BOJ (Java) 1600번: 말이 되고픈 원숭이

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

---

풀이

원숭이가 K번까지는 말처럼 뛸 수 있다. 따라서 K번 뛰기 전까지는 같은 구역에 몇 번이고 방문할 수 있다. <- 이 부분이 핵심이다.

따라서 bfs에서 방문 체크를 할 때 K 번까지 가능하게 해야 하므로 각 좌표마다 K번 체크할 수 있게 visited 배열을 3차원으로 만들어야 한다. 

이 때 K번을 다 뛰었음에도 계속 갈 수 있으므로 visited 배열의 크기는 [H][W][K + 1]개로 선언되어야 한다.

이 외에는 bfs 알고리즘과 동일하며, 시작 지점과 출발 지점이 같을 때의 예외 처리가 필요하다.

---

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    static int[][] map;
    static int[][] horse = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}};
    static int[][] mv = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int K, H, W;
    static boolean[][][] visited;
    public static void main(String args[]) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(bf.readLine());

        String[] inputs = bf.readLine().split(" ");
        W = Integer.parseInt(inputs[0]);
        H = Integer.parseInt(inputs[1]);

        if (W == 1 && H == 1) {
            System.out.println(0);
            return;
        }
        map = new int[H][W];
        visited = new boolean[H][W][K + 1];
        for (int i = 0; i < H; i++) {
            inputs = bf.readLine().split(" ");
            for (int j = 0; j < W; j++) {
                map[i][j] = Integer.parseInt(inputs[j]);
            }
        }

        Queue<Cor> q = new ArrayDeque<>();
        q.add(new Cor(0, 0, 0, 0));
        visited[0][0][0] = true;
        while (!q.isEmpty()) {
            Cor now = q.poll();
//            System.out.println(now.toString());
            if (now.horseCnt < K) {
                for (int i = 0; i < 8; i++) {
                    int nr = now.r + horse[i][0];
                    int nc = now.c + horse[i][1];

                    if (nr < 0 || nc < 0 || H <= nr || W <= nc || map[nr][nc] == 1 || visited[nr][nc][now.horseCnt + 1]) continue;
                    visited[nr][nc][now.horseCnt + 1] = true;
                    if (nr == H - 1 && nc == W - 1) {
                        System.out.println(now.cnt + 1);
                        return;
                    }
                    q.add(new Cor(nr, nc, now.horseCnt + 1, now.cnt + 1));

                }
            }

            for (int i = 0; i < 4; i++) {
                int nr = now.r + mv[i][0];
                int nc = now.c + mv[i][1];

                if (nr < 0 || nc < 0 || H <= nr || W <= nc || map[nr][nc] == 1 || visited[nr][nc][now.horseCnt]) continue;
                visited[nr][nc][now.horseCnt] = true;
                if (nr == H - 1 && nc == W - 1) {
                    System.out.println(now.cnt + 1);
                    return;
                }
                q.add(new Cor(nr, nc, now.horseCnt,now.cnt + 1));
            }
        }
        System.out.println(-1);
    }

    static class Cor {
        int r;
        int c;
        int horseCnt;
        int cnt;

        public Cor(int r, int c, int horseCnt, int cnt) {
            this.r = r;
            this.c = c;
            this.horseCnt = horseCnt;
            this.cnt = cnt;
        }
    }

}