[BaekJoon] 2159 케익 배달 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int SIZE = 100_000;

    static int customerCount;
    static int[] start;
    static int[][] customers;
    static int[] dx = {0, -1, 0, 1, 0};
    static int[] dy = {0, 0, -1, 0, 1};

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

        customerCount = scanner.nextInt();
        customers = new int[customerCount][2];
        start = new int[]{scanner.nextInt(), scanner.nextInt()};

        for (int idx = 0; idx < customerCount; idx++) {
            customers[idx] = new int[]{scanner.nextInt(), scanner.nextInt()};
        }
    }

    /*
     * 입력으로 주어진 순서대로 배달을 진행해야하기 때문에 바로 다음 고객까지의 거리를 구해 누적해나가며 최단 거리를 구한다
     * 한 고객으로부터 바로 다음 고객까지의 최단 거리는 |x2 - x1| + |y2 - y1|가 될 것이다
     * 그런데 배달은 고객의 상하좌우 인접 위치에 해도 되기 때문에 한 고객으로부터 바로 다음 고객으로까지 나올 수 있는 모든 거리는 한 고객의 위치 및 상하좌우 위치에서
     * 바로 다음 고객의 위치 및 상하좌우 위치까지의 거리, 총 25가지 경우가 된다
     * 이 경우들을 DP를 이용하여 누적해나가며 마지막 고객에게까지 배달을 완료하였을 때 5개의 위치 중 가장 최단 거리를 찾는다
     * dp[customer][dir] = 시작부터 customer 고객에게 dir 위치로 배달하였을 때 최단 거리
     *  - dir : 방향
     *      - 0 : 고객 위치
     *      - 1 : 위 방향
     *      - 2 : 왼쪽 방향
     *      - 3 : 아래 방향
     *      - 4 : 오른쪽 방향
     */
    static void solution() {
        long[][] distances = new long[customerCount][dx.length];
        initDistances(distances);
        calculateMinimumDistances(distances);
        long min = Arrays.stream(distances[customerCount - 1]).min().getAsLong();
        System.out.println(min);
    }

    static void initDistances(long[][] distances) {
        for (int row = 0; row < customerCount; row++) {
            Arrays.fill(distances[row], Long.MAX_VALUE);
        }

        for (int dir = 0; dir < dx.length; dir++) {
            int cx = customers[0][0] + dx[dir];
            int cy = customers[0][1] + dy[dir];

            if (isInMap(cx, cy)) {
                distances[0][dir] = Math.abs(start[0] - cx) + Math.abs(start[1] - cy);
            }
        }
    }

    static void calculateMinimumDistances(long[][] distances) {
        for (int customerIdx = 1; customerIdx < customerCount; customerIdx++) {
            calculateEachCustomerMinimumDistances(customerIdx, distances);
        }
    }

    static void calculateEachCustomerMinimumDistances(int customerIdx, long[][] distances) {
        for (int prevDir = 0; prevDir < dx.length; prevDir++) {
            if (distances[customerIdx - 1][prevDir] == Integer.MAX_VALUE) {
                continue;
            }

            calculateEachLocationMinimumDistances(customerIdx, prevDir,
                    new int[]{customers[customerIdx - 1][0] + dx[prevDir], customers[customerIdx - 1][1] + dy[prevDir]},
                    distances);
        }
    }

    static void calculateEachLocationMinimumDistances(int customerIdx, int prevDir, int[] location,
                                                      long[][] distances) {
        for (int dir = 0; dir < dx.length; dir++) {
            int cx = customers[customerIdx][0] + dx[dir];
            int cy = customers[customerIdx][1] + dy[dir];
            int dist = Math.abs(location[0] - cx) + Math.abs(location[1] - cy);
            distances[customerIdx][dir] = Math.min(distances[customerIdx][dir],
                    distances[customerIdx - 1][prevDir] + dist);
        }
    }

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

    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());
        }
    }
}