말이 되고픈 원숭이 - 1600번

 

---

풀이 방법

BFS를 이용해서 최단경로를 구하는 방법을 이용했다.

이동할 수 있는 동작마다 if문을 이용해서 우선순위 큐에 넣어주었다.

여기서 방문을 체크하는 visited를 조심해야 했다.

그냥 테이블과 동일하게 visited를 구현하게 되면 말처럼 움직이는 동작과 그냥 인접한 칸으로 움직이는 동작을 구분하지 않게 된다.

그래서 말처럼 움직이는 동작을 한 횟수별로 따로 visited 테이블을 만들어주어야 한다.

나머지는 기본 BFS 동일하게 풀이하면 된다.

 

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
    private int x;
    private int y;
    private int cnt;
    private int K_count;

    public Node(int x, int y, int cnt, int k_count) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        K_count = k_count;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getCnt() {
        return cnt;
    }

    public int getK_count() {
        return K_count;
    }

    @Override
    public int compareTo(Node other) {
        if (this.cnt < other.cnt)
            return -1;
        return 1;
    }
}


public class Main {
    static int[][] arr;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

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

        st = new StringTokenizer(br.readLine());

        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
        int count = -1;

        arr = new int[H][W];

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

        Boolean[][][] visited = new Boolean[K + 1][H][W];

        for (int i = 0; i <= K; i++) {
            for (int j = 0; j < H; j++) {
                Arrays.fill(visited[i][j], false);
            }
        }

        Node start = new Node(0, 0, 0, 0);
        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.offer(start);

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int x = node.getX();
            int y = node.getY();
            int K_count = node.getK_count();
            int cnt = node.getCnt();

            if (visited[K_count][y][x] == true)
                continue;

            visited[K_count][y][x] = true;

            if (y == H - 1 && x == W - 1) {
                count = cnt;
                break;
            }

            if (K_count < K) {
                if (x + 1 < W && y - 2 >= 0 && arr[y - 2][x + 1] != 1) {
                    pq.offer(new Node(x + 1, y - 2, cnt + 1, K_count + 1));
                }
                if (x + 2 < W && y - 1 >= 0 && arr[y - 1][x + 2] != 1) {
                    pq.offer(new Node(x + 2, y - 1, cnt + 1, K_count + 1));
                }
                if (x + 2 < W && y + 1 < H && arr[y + 1][x + 2] != 1) {
                    pq.offer(new Node(x + 2, y + 1, cnt + 1, K_count + 1));
                }
                if (x + 1 < W && y + 2 < H && arr[y + 2][x + 1] != 1) {
                    pq.offer(new Node(x + 1, y + 2, cnt + 1, K_count + 1));
                }
                if (x - 1 >= 0 && y + 2 < H && arr[y + 2][x - 1] != 1) {
                    pq.offer(new Node(x - 1, y + 2, cnt + 1, K_count + 1));
                }
                if (x - 2 >= 0 && y + 1 < H && arr[y + 1][x - 2] != 1) {
                    pq.offer(new Node(x - 2, y + 1, cnt + 1, K_count + 1));
                }
                if (x - 2 >= 0 && y - 1 >= 0 && arr[y - 1][x - 2] != 1) {
                    pq.offer(new Node(x - 2, y - 1, cnt + 1, K_count + 1));
                }
                if (x - 1 >= 0 && y - 2 >= 0 && arr[y - 2][x - 1] != 1) {
                    pq.offer(new Node(x - 1, y - 2, cnt + 1, K_count + 1));
                }
            }

            if (x + 1 < W && arr[y][x + 1] != 1) {
                pq.offer(new Node(x + 1, y, cnt + 1, K_count));
            }
            if (x - 1 >= 0 && arr[y][x - 1] != 1) {
                pq.offer(new Node(x - 1, y, cnt + 1, K_count));
            }
            if (y + 1 < H && arr[y + 1][x] != 1) {
                pq.offer(new Node(x, y + 1, cnt + 1, K_count));
            }
            if (y - 1 >= 0 && arr[y - 1][x] != 1) {
                pq.offer(new Node(x, y - 1, cnt + 1, K_count));
            }
        }

        System.out.println(count);
    }
}