[백준]1600: 말이 되고픈 원숭이 - JAVA

[백준]1600: 말이 되고픈 원숭이

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

풀이

출발 위치에서 도착위치까지 움직일 수 있는 최소 값을 반환하는 문제이므로 BFS를 사용하였다. 

 

이때 말이 움직일 수 있는 위치와 원숭이가 움직일 수 있는 위치를 따로 배열로 만들어 주었다. 최소값을 계산할 때는 한번 방문한 위치는 재 방문해서 안되기 때문에 visited배열을 선언하여 재 방문을 허용하지 않도록 하였다.

 

이때 단순히 visited배열을 2차원으로 선언해 주면 인접 노드로 이동했을 때와 말이 이동할 수 있는 위치로 이동했을 때 서로 다른 경로로 방문했지만 이를 구별할 수 없어 무조건 한번 방문한 곳은 다시 방문할 수 없다. 

 

즉, 서로 다른 경로로 이동했을때의 visited처리를 따로 해주는 것이 필요하고 이를 위해 visited배열을 3차원으로 선언해 주었다. 각각의 인덱스는 visited[x좌표][y좌표][k번이동한횟수]가 된다. 

 

k가 0보다 크다면 말로 이동할 수 있는 위치로 움직일 수 있으므로 이동시켜 주었고 그렇지 않다면 인접 노드로만 이동하도록 하였다. 그리고 도착 위치에 도달하면 현재 count를 반환해주었다.

 

코드

import java.util.*;
 
public class Main {
    
    static int k, w, h;
    static int[][] board;
    static int min = Integer.MAX_VALUE;
    static int[] hdx = {-2, -2, -1, -1, 1, 1, 2, 2}; //말이 이동할 수 있는 8방향
    static int[] hdy = {-1, 1, -2, 2, -2, 2, -1, 1};
    static int[] dx = {0, 1, 0 ,-1}; // 원숭이가 이동할 수 있는 4방향
    static int[] dy = {1, 0, -1, 0};
    static boolean[][][] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
    
        k = scan.nextInt();
        w = scan.nextInt();
        h = scan.nextInt();
        
        board = new int[h][w];
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                board[i][j] = scan.nextInt();
            }
        }
        
        visited = new boolean[h][w][k + 1];
        min = bfs(0, 0);
        
        if(min == Integer.MAX_VALUE) System.out.println("-1");
        else System.out.println(min);
    }
    
    public static int bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y, 0, k)); 
        visited[x][y][k] = true;
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            if(current.x == h - 1 && current.y == w - 1) return current.count; 
            
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                if(nx >= 0 && ny >= 0 && nx < h && ny < w && !visited[nx][ny][current.k] && board[nx][ny] == 0) {
                    visited[nx][ny][current.k] = true;
                    q.offer(new Node(nx, ny, current.count + 1, current.k));
                }
            }
            
            if(current.k > 0) {
                for(int i = 0; i < 8; i++) {
                    int nx = current.x + hdx[i];
                    int ny = current.y + hdy[i];
                    if(nx >= 0 && ny >= 0 && nx < h && ny < w && !visited[nx][ny][current.k - 1] && board[nx][ny] == 0) {
                        visited[nx][ny][current.k - 1] = true;
                        q.offer(new Node(nx, ny, current.count + 1, current.k - 1));
                    }
                }
            }
        }
        return min;
    }
    
    public static class Node {
        int x;
        int y;
        int count;
        int k;
        
        public Node(int x, int y, int count, int k) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.k = k;
        }
    }
}