[BaekJoon] 14461 소가 길을 건너간 이유 7 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static final int MAX_CROSS_COUNT = 3;

    static int size;
    static int crossTime;
    static int[][] pastures;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    static void input() {
        Reader scanner = new Reader();

        size = scanner.nextInt();
        crossTime = scanner.nextInt();
        pastures = new int[size][size];

        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                pastures[row][col] = scanner.nextInt();
            }
        }
    }

    /*
     * 시작 지점((0, 0) 지점)부터 도착 지점((N - 1, N - 1))까지 인접한 네 곳으로 이동해보며
     * 각 지점에서의 최소 시간을 배열에 저장한다 -> 이 배열을 통해 (N - 1, N - 1) 지점에서의 최소 시간을 구한다
     * 이때, 최소 시간을 저장하는 배열을 3차원 배열을 이용한다
     *  - 각 위치의 x, y좌표를 나타내는 값과 이동 횟수에 대한 값을 이용하여 3차원 배열을 만든다
     *  - 특정 지점에 대한 최소 시간을 저장할 때 이동 횟수를 신경쓰지 않는다면 최소 시간이 되는 경로가
     *    특정 지점에서 최소 시간이 되지 않아 끊기는 경우가 발생한다
     *      - 특정 지점에서 이동 횟수가 3이 되면 해당 지점에 있는 풀을 먹는 시간을 추가해줘야 하는데, 이로 인해 최소 시간이 되지 않을 수 있다
     *  - 그러므로 각 지점에서 이동 횟수에 따라 최소 시간을 구한다
     * (N - 1, N - 1) 지점에서 이동 횟수에 따른 최소 시간들 중 최소값이 시작 지점부터 도착 지점까지의 최소 시간이 된다
     */
    static void solution() {
        System.out.println(calculateCrossingTimes());
    }

    static long calculateCrossingTimes() {
        Queue<Pasture> queue = new PriorityQueue<>();
        long[][][] times = new long[size][size][MAX_CROSS_COUNT];
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                Arrays.fill(times[row][col], Long.MAX_VALUE);
            }
        }

        queue.offer(new Pasture(0, 0, 0, 0));
        times[0][0][0] = 0;

        while (!queue.isEmpty()) {
            Pasture cur = queue.poll();

            if (times[cur.x][cur.y][cur.moveCount] < cur.time) {
                continue;
            }

            for (int dir = 0; dir < dx.length; dir++) {
                int cx = cur.x + dx[dir];
                int cy = cur.y + dy[dir];

                if (isInMap(cx, cy)) {
                    long nextTime = cur.time + crossTime;
                    int nextCrossCount = cur.moveCount + 1;

                    if (nextCrossCount == MAX_CROSS_COUNT) {
                        nextTime += pastures[cx][cy];
                        nextCrossCount = 0;
                    }

                    if (times[cx][cy][nextCrossCount] > nextTime) {
                        times[cx][cy][nextCrossCount] = nextTime;
                        queue.offer(new Pasture(cx, cy, nextCrossCount, nextTime));
                    }
                }
            }
        }

        return Arrays.stream(times[size - 1][size - 1]).min().getAsLong();
    }

    static boolean isInMap(int x, int y) {
        return x >= 0 && x < size && y >= 0 && y < size;
    }

    static class Pasture implements Comparable<Pasture> {
        int x;
        int y;
        int moveCount;
        long time;

        public Pasture(int x, int y, int moveCount, long time) {
            this.x = x;
            this.y = y;
            this.moveCount = moveCount;
            this.time = time;
        }

        @Override
        public int compareTo(Pasture p) {
            if (time < p.time) {
                return -1;
            }
            if (time > p.time) {
                return 1;
            }
            return 0;
        }
    }

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

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}