[Problem Solving] BOJ 1600 : 말이 되고픈 원숭이

문제 링크 : https://www.acmicpc.net/problem/1600

 

(0, 0) 에서 (H - 1, W - 1)까지 가는 최단시간을 구하는 문제인데, 이동중에 hdy와 hdx를 이용한 이동, 즉 jump를 최대 K번 할 수 있는 문제이다.

 

Point 클래스에 좌표 y, x랑, jump를 몇번 해왔는지를 표시할 jumpCount 필드를 추가한다.

dist[i][j][k]는 (i, j) 칸에 오기까지 점프를 k번 했을 때, 걸린 최소 시간이다.

 

문제에서 구하고자 하는 것은 dist[H - 1][W - 1][i](0 <= i <= K) 중에서 가장 작은 값을 구하는 것이다.

 

1. bfs는 일반적으로 (0, 0) 에서 (H - 1, W - 1)까지 가는 최단시간을 구하는 문제에서 구현하는 것처럼 먼저 구현을 한다.

2. cur.jumpCount가 K보다 작다면, 다음 Point인 next를 (cur.y + hdy[i], cur.x + hdx[i], cur.jumpCount + 1)로 설정하고 유효한 위치이고 최단시간이라면 갱신 후 큐에 추가한다.

3. bfs를 수행이 끝나면 dist[H - 1][W - 1][i](0 <= i <= K) 중에서 가장 작은 값을 구한다. 가장 작은 값을 구했는데 987654321 이면 -1을 출력하고, 그렇지 않다면 가장 작은 값을 출력한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main 
{
    public static class Point 
    {
        public int y;
        public int x;
        public int jumpCount;

        public Point(int y, int x, int jumpCount)
        {
            this.y = y;
            this.x = x;
            this.jumpCount = jumpCount;
        }
    }
    public static int K, W, H;
    public static int board[][];
    public static int dist[][][];
    public static int dy[] = {-1, 1, 0, 0};
    public static int dx[] = {0, 0, -1, 1};
    public static int hdy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
    public static int hdx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
    public static Queue<Point> queue = new LinkedList<>();

    public static void input() throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        W = Integer.parseInt(line[0]);
        H = Integer.parseInt(line[1]);
        board = new int[H][W];
        dist = new int[H][W][K + 1];
        for(int i = 0; i < H; i++)
        {
            line = br.readLine().split(" ");
            for(int j = 0; j < W; j++)
            {
                board[i][j] = Integer.parseInt(line[j]);
                for(int k = 0; k <= K; k++)
                {
                    dist[i][j][k] = 987654321;
                }
            }
        }
        br.close();
    }

    public static boolean valid(int y, int x)
    {
        return (0 <= y && y < H && 0 <= x && x < W && board[y][x] != 1);
    }

    public static void bfs()
    {
        Point s = new Point(0, 0, 0);
        dist[s.y][s.x][s.jumpCount] = 0;
        queue.add(s);

        while(!queue.isEmpty())
        {
            Point cur = queue.peek();
            queue.remove();

            if(cur.jumpCount < K)
            {
                for(int i = 0; i < 8; i++)
                {
                    Point next = new Point(cur.y + hdy[i], cur.x + hdx[i], cur.jumpCount + 1);
                    if(valid(next.y, next.x))
                    {
                        if(dist[next.y][next.x][next.jumpCount] > dist[cur.y][cur.x][cur.jumpCount] + 1)
                        {
                            dist[next.y][next.x][next.jumpCount] = dist[cur.y][cur.x][cur.jumpCount] + 1;
                            queue.add(next);
                        }
                    }
                }
            }

            for(int i = 0; i < 4; i++)
            {
                Point next = new Point(cur.y + dy[i], cur.x + dx[i], cur.jumpCount);
                if(valid(next.y, next.x))
                {
                    if(dist[next.y][next.x][next.jumpCount] > dist[cur.y][cur.x][cur.jumpCount] + 1)
                    {
                        dist[next.y][next.x][next.jumpCount] = dist[cur.y][cur.x][cur.jumpCount] + 1;
                        queue.add(next);
                    }
                }
            }
        }
    }

    public static void solution()
    {
        bfs();
    }

    public static void output()
    {
        int answer = 987654321;
        for(int i = 0; i <= K; i++)
        {
            answer = Math.min(answer, dist[H - 1][W - 1][i]);
        }

        if(answer == 987654321)
        {
            System.out.println(-1);
        }
        else
        {
            System.out.println(answer);
        }
    }

    public static void main(String[] args) throws IOException
    {
        input();
        solution();
        output();
    }
}