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

 

풀이

처음엔 DP 문제라고 생각했으나, 부분 문제의 최적의 해가 전체 솔루션의 최적의 해가 될 수 없겠다는 생각이 들었다. 가령 아래와 같은 경우, K = 1이라고 가정해보자. 좌측 상단의 끝점이 [0,0]이라고 가정한다면 [1,2]까지의 최적해는 1이 된다. 

0000
0000
1111
1110

 

반면 [0,0]부터 [1,2]를 거치고, [3,3]으로 가는 경우는 4가 된다. 그렇지만 이 단계에서의 [1,2]까지의 최적해는 3이다. K를 [0,0] -> [1,2]에 소모한다면 벽을 넘어갈 수 없기 때문이다. 따라서 탐색 문제라는 생각이 들어서 BFS로 해결할 수 없을지 고민했다.

 

일반적인 완전탐색과 다른 점은 K를 동적으로 사용할 수 있다는 점이다. 말처럼 이동하느냐 마냐에 따라 해당 격자까지의 거리가 달라진다. 처음엔 방문했는지 여부를 판단하는 visited 배열을 2차원으로 유지했었는데, 이 점 때문에 틀렸었다. 즉, 말처럼 이동을 했는지, 혹은 얼마나 말처럼 이동했는지 여부를 판단할 수 없었다.

 

따라서 visited[x][y][k] 처럼 3차원 visited 배열을 활용한다. 단순히 visited 2차원 배열을 2개(말 이동, 원숭이 이동) 유지하는 것으로 풀기 어려운 이유는, 말처럼 한 번 이동하고 나서 원숭이처럼 이동하는 경우를 생각해보면 쉽다. 이는 원숭이처럼만 이동하는 경우와 구별이 되어야 하기 때문에 점프 횟수에 따라 구분되어야 할 필요가 있다.

 

코드

public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(reader.readLine());
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        int[][] matrix = new int[H][W];
        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(reader.readLine());
            for (int j = 0; j < W; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        boolean[][][] visited = new boolean[H][W][K + 1];
        int[][] count = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                count[i][j] = Integer.MAX_VALUE;
            }
        }
        if (matrix[0][0] != 1) {
            count[0][0] = 0;
        }

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0, 0, 0));
        visited[0][0][0] = true;

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        int[] horseDx = {-2, -2, -1, -1, 1, 1, 2, 2};
        int[] horseDy = {-1, 1, -2, 2, -2, 2, -1, 1};

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            if (point.x == H - 1 && point.y == W - 1) {
                break;
            }

            for (int i = 0; i < 4; i++) {
                int x = dx[i] + point.x;
                int y = dy[i] + point.y;

                if (x < 0 || y < 0 || x >= H || y >= W) {
                    continue;
                } else if (visited[x][y][point.horseCount] || matrix[x][y] == 1) {
                    continue;
                }
                visited[x][y][point.horseCount] = true;
                count[x][y] = count[point.x][point.y] + 1;
                queue.add(new Point(x, y, point.horseCount));
            }

            for (int i = 0; i < 8; i++) {
                int x = horseDx[i] + point.x;
                int y = horseDy[i] + point.y;

                if (x < 0 || y < 0 || x >= H || y >= W) {
                    continue;
                } else if (point.horseCount >= K) {
                    break; // K번 넘어가면 안됨
                } else if (visited[x][y][point.horseCount + 1] || matrix[x][y] == 1) {
                    continue;
                }

                count[x][y] = count[point.x][point.y] + 1;
                visited[x][y][point.horseCount + 1] = true;
                queue.add(new Point(x, y, point.horseCount + 1));
            }
        }

        System.out.println(count[H - 1][W - 1] != Integer.MAX_VALUE ?
                count[H - 1][W - 1] : -1);
    }

    static class Point {
        int x;
        int y;
        int horseCount;

        public Point(int x, int y, int horseCount) {
            this.x = x;
            this.y = y;
            this.horseCount = horseCount;
        }
    }