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

BOJ 말이 되고픈 원숭이 : https://www.acmicpc.net/problem/1600

안녕하세요. 이번 문제는 백준 온라인 저지의 [말이 되고픈 원숭이] 입니다.

BFS를 단순하게 사용하면 풀릴 것 같지만, 함정이 있었습니다.

말처럼 움직였을때의 위치와, 그냥 한번 움직였을 때의 위치가 같을 경우에,

좌표가 같아도 그 경로가 다를 수 있습니다.

쉽게말해서 말의 움직임을 아껴놨다가 사용해야할 경우가 생길 수 있습니다.

하지만 먼저 기회를 사용해 해당 좌표에 도달한 것을 체크한다면,

나중에 기회를 아꼈을 경우 해당 좌표가 Visited되있어 재방문을 할 수 없습니다.

그래서 Visited를 3차원으로 만들었습니다.

import java.util.*;
class Node {
    public int i, j, depth, chance;
    Node(int i, int j, int depth, int chance) {
        this.i = i;
        this.j = j;
        this.depth = depth;
        this.chance = chance;
    }
}
public class Main {
    public static int K, W, H;
    public static int[][] Map = new int[200][200];
    public static boolean[][][] Visited = new boolean[200][200][31];
    public static Queue<Node> q = new LinkedList<Node>();
    public static int[][] d = { { -1, 0}, {1, 0}, {0, -1}, {0, 1} };
    public static int[][] horse_d = { {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2} };
    public static boolean is_bound(int h, int w) {
        return h >= 0 && h < H && w >= 0 && w < W;
    }
    public static int BFS() {
        while(!q.isEmpty()) {
            Node node = q.poll();
            if(node.i == H-1 && node.j == W-1) {
                return node.depth;
            }
            for(int k = 0; k < 8; k++) {
                int next_i = node.i + horse_d[k][0];
                int next_j = node.j + horse_d[k][1];
                if(is_bound(next_i, next_j) && node.chance < K) {
                    if(!Visited[next_i][next_j][node.chance + 1] && Map[next_i][next_j] == 0) {
                        Visited[next_i][next_j][node.chance + 1] = true;
                        Node new_node = new Node(next_i, next_j, node.depth + 1, node.chance + 1);
                        q.offer(new_node);
                    }
                }
            }
            for(int k = 0; k < 4; k++) {
                int next_i = node.i + d[k][0];
                int next_j = node.j + d[k][1];
                if(is_bound(next_i, next_j)) {
                    if(!Visited[next_i][next_j][node.chance] && Map[next_i][next_j] == 0) {
                        Visited[next_i][next_j][node.chance]= true;
                        Node new_node = new Node(next_i, next_j, node.depth+ 1, node.chance);
                        q.offer(new_node);
                    }
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        K = sc.nextInt();
        W = sc.nextInt();
        H = sc.nextInt();
        for(int h = 0; h < H; h++) {
            for(int w = 0; w< W; w++) {
                Map[h][w] = sc.nextInt();
            }
        }
        for(int k = 0; k <= K; k++)
            Visited[0][0][k] = true;
        Node first_node = new Node(0, 0, 0, 0);
        q.offer(first_node);
        System.out.println(BFS());
    }
}