[백준] 1600번 : 말이 되고픈 원숭이 - 자바(JAVA)

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

1600번: 말이 되고픈 원숭이

 

문제 해석

말은 격자판에서 체스의 나이트와 같은 이동방식을 가집니다.

X 표시한 곳은 말이 갈 수 있는 위치이며 말은 장애물을 뛰어넘을 수 있습니다.

말의 이동(https://www.acmicpc.net/problem/1600)

하지만 원숭이는 능력이 부족해서 k번만 말처럼 움직일 수 있고 ,그 외에는 그냥 인접한 칸으로 움직일 수 있습니다.

인접한칸은 상하좌우를 의미합니다.

 

원숭이는 맨 왼쪽위에서 시작해서 맨 오른쪽 아래로 가려고 합니다.

최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내세요

 

평지는 0 , 장애물은 1로 표시합니다.

장애물로는 이동할 수 없습니다.

격자판은 W x H 로 주어집니다.

시작점과 도착점은 항상 평지입니다.

W,H는 200이하입니다.

 

문제 풀이 전 설계

이동할 수 있는 방법이 2가지가 존재합니다.

말처럼 이동, 인접칸으로 이동

 

말처럼 이동했을때 도착지를 지나갈 수 있으며, 인전칸으로 이동하는 경우에도 말처럼 이동했을 때 도착지를 도착하는 경우가 발생한다면 최소한의 동작이 아니게 됩니다.

 

따라서 움직일 수 있는 가능성을 모두 열어두어야 합니다.

 

예를들어 어떤칸을 기준으로 해당칸은 말처럼 이동을 해서 도착했을 수도있고, 원숭이처럼 이동해서 도착했을 수도 있습니다. 아니면 두 방식을 섞어서 도착했을 수도 있습니다.

 

따라서 일반적인 visited 배열보다는 다차원의 visited배열이 필요할것같습니다.

visited[y좌표][x좌표][남은k의개수]

 

 

코드

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

public class Main_1600_말이되고픈원숭이 {

    static class Pos {
        int y;
        int x;
        int remainK;
        int step;

        public Pos(int y, int x, int remainK, int step) {
            this.y = y;
            this.x = x;
            this.remainK = remainK;
            this.step = step;
        }

    }

    static int[] monkeyDy = {-1, 1, 0, 0};
    static int[] monkeyDx = {0, 0, -1, 1};
    static int[] hourseDy = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[] hourseDx = {-2, -1, 1, 2, -2, -1, 1, 2};
    static int[][] board;
    static int width, height;
    static boolean[][][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        width = Integer.parseInt(st.nextToken());
        height = Integer.parseInt(st.nextToken());

        board = new int[height][width];

        for (int y = 0; y < height; y++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int x = 0; x < width; x++) {
                    board[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        visited = new boolean[height][width][K+1];

        int result = -1;
        Queue<Pos> bfsQ = new LinkedList<>();
        bfsQ.add(new Pos(0, 0, K, 0));

        while (!bfsQ.isEmpty()) {
            Pos curPos = bfsQ.poll();
            int curY = curPos.y;
            int curX = curPos.x;
            if (curY == height - 1 && curX == width - 1) {
                //목적지 도착
                result = curPos.step;
                break;
            }
            int tempY, tempX;
            for (int k = 0; k < 4; k++) {
                tempY = curY + monkeyDy[k];
                tempX = curX + monkeyDx[k];
                if(!isValid(tempY,tempX,curPos.remainK)){
                    continue;
                }
                visited[tempY][tempX][curPos.remainK] = true;
                bfsQ.add(new Pos(tempY,tempX,curPos.remainK,curPos.step+1));

            }
            if(curPos.remainK <= 0){
                continue;
            }
            for(int k=0; k<8; k++){
                tempY = curY + hourseDy[k];
                tempX = curX + hourseDx[k];
                if(!isValid(tempY,tempX,curPos.remainK-1)){
                    continue;
                }
                visited[tempY][tempX][curPos.remainK-1] = true;
                bfsQ.add(new Pos(tempY,tempX,curPos.remainK-1,curPos.step+1));
            }

        }

        System.out.println(result);


    }

    private static boolean isValid(int tempY, int tempX, int remainK) {
        return tempY >=0 && tempX >=0 && tempY <height && tempX < width && !visited[tempY][tempX][remainK] && board[tempY][tempX] ==0;
    }


}