백준 1620 - 말이 되고픈 원숭이

문제

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

리뷰

원숭이는 상하좌우로 이동하거나 말처럼 이동할 수 있다.
다만, 여기서 생각해야할 점은 $K$번만큼 말처럼 이동했을 경우의 경로와
그 외의 경로를 구분하여 방문 처리를 해주어야 한다는 점이다. $K$번, 말처럼
이동한 경우에 따른 모든 경로에서 최단 경로를 도출해낼 수 있다.

이를 구현하기 위해 방문 처리 배열 visited 를 $(K+1) \times H \times W$
형태로 선언했으며 경로를 표현하기 위해 Node 클래스를 정의하고 그 필드로
현재 경로에서 말처럼 이동한 횟수인 horseCount를 설정하였다.

그리고 bfs내에서 $K$(horseCount)에 따라서 visited 처리를 따로 하고
가장 먼저 도착 지점에 도달하는 경로의 비용을 반환하도록 구현했다.

로직의 시간복잡도는 bfs의 복잡도인 $O(K \times H \times W)$로 수렴하므로
최악의 경우인 $30 \times 200 \times 200$의 경우에도 제한 조건을 무난히
통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static int K, W, H;
    static int[][] map;
    static boolean[][][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        K = parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        W = parseInt(st.nextToken());
        H = parseInt(st.nextToken());
        map = new int[H][W];
        visited = new boolean[K + 1][H][W];

        for (int y = 0; y < H; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < W; x++)
                map[y][x] = parseInt(st.nextToken());
        }

        int result = bfs();
        System.out.println(result);
        br.close();
    }

    static int bfs() { // O(K x H x W)
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int[] hx = {1, 2, 2, 1, -1, -2, -2, -1};
        int[] hy = {-2, -1, 1, 2, 2, 1, -1, -2};

        Queue<Node> queue = new ArrayDeque<>();
        visited[0][0][0] = true;
        queue.offer(new Node(0, 0, 0, 0));

        int nx, ny;

        while (!queue.isEmpty()) {
            Node node = queue.poll();


            if (node.x == W - 1 && node.y == H - 1)
                return node.level;

            for (int i = 0; i < dx.length; i++) {
                nx = node.x + dx[i];
                ny = node.y + dy[i];

                if (isOutBound(nx, ny))
                    continue;

                if (map[ny][nx] == 1)
                    continue;

                if (!visited[node.horseCount][ny][nx]) {
                    visited[node.horseCount][ny][nx] = true;
                    queue.offer(new Node(nx, ny, node.level + 1, node.horseCount));
                }
            }

            if (node.horseCount + 1 > K)
                continue;


            for (int i = 0; i < hx.length; i++) {
                nx = node.x + hx[i];
                ny = node.y + hy[i];

                if (isOutBound(nx, ny))
                    continue;

                if (map[ny][nx] == 1)
                    continue;

                if (!visited[node.horseCount + 1][ny][nx]) {
                    visited[node.horseCount + 1][ny][nx] = true;
                    queue.offer(new Node(nx, ny, node.level + 1, node.horseCount + 1));
                }
            }
        }

        return -1;
    }

    static boolean isOutBound(int x, int y) {
        return x < 0 || x >= W || y < 0 || y >= H;
    }

    static class Node {
        int x, y, level, horseCount;

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

결과