백준 2159 (케익 배달) - java

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

2159번: 케익 배달

 

문제

프랑스에서 공부를 하고 돌아온 선아는 자신이 그렇게도 되고 싶어 했던 파티셰가 되었다. 케익 배달 전문업체 보나뻬띠에 취직한 선아는 친절하게도 자신이 만든 케익을 고객들에게 직접 배달을 하려 한다. N명의 고객에게 케익을 배달하는데 주문이 들어온 순서대로 배달하기를 원하며 고객이 케익을 받을 수 있을 만큼 충분히 가까이까지 배달한다.

N명의 고객의 위치는 순서대로 100,000×100,000 격자의 정수 좌표로 주어지고 처음 출발하게 되는 보나뻬띠의 위치도 정수 좌표로 주어진다. 선아는 격자 위에서 상하좌우로만 움직이며 고객에게 케익을 전달하기 위해서는 그 고객의 위치까지 가거나 고객의 상하좌우 인접 격자점에 가야 한다. 이때 선아가 최단거리를 이동하여 입력된 순서대로 배달을 끝낼 수 있는 거리를 계산하는 프로그램을 작성하시오. 여기서 거리는 격자 상의 칸 수를 말한다.

 

위의 예에서 선아는 11칸을 움직여서 세 명의 고객에게 배달을 마칠 수 있다. 선아는 반드시 고객들에게 순서대로 배달을 하며 순서에 어긋난 사람에게 배달을 할 수 있는 위치에 있더라도 케익을 주지 않고 순서대로 배달을 한다. 고객의 위치는 중복이 될 수도 있다.

 

유형 : 다이나믹 프로그래밍

 

접근 방식

• 우선 100_000 * 100_000 격자이기 때문에 격자를 배열로 표현하고 그래프 탐색을 한다면 메모리 초과를 맛보게 될 것이다 ㅎㄷㄷ
  • 사실 정해진 순서로만 케익을 전달하고 중앙 , 상 , 하 , 좌 , 우의 위치만 알면 된다.
  • 그리고 장애물 또한 존재하지 않기 때문에 맨허튼 거리 공식을 사용하면 된다.
• DP의 식은 간단하다. dp[i][j] : i번 째 위치의 중앙 , 상 , 하 , 좌 , 우 위치까지 가는데 걸린 최단 거리
  • dp[i][j] = dp[i-1][k] + calDis( i-1 ~ i )
    • 즉 이전 위치의 중앙 , 상 , 하 , 좌 , 우 위치에서 다음 위치까지의 거리이다. 

전체 코드

package DP;

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

// BOJ_2159_케익_배달 G2
// 2024_02_08
// time : 464 ms
// memory : 46028 KB

public class BOJ_2159_케익_배달 {
    static int[] dx = {0, 1, -1, 0, 0};
    static int[] dy = {0, 0, 0, 1, -1};
    static int n = 0;

    static final long MAX = Long.MAX_VALUE;
    static int[][] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");

        int sx = Integer.parseInt(st.nextToken());
        int sy = Integer.parseInt(st.nextToken());

        board = new int[n + 1][2];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int tmpX = Integer.parseInt(st.nextToken());
            int tmpY = Integer.parseInt(st.nextToken());

            board[i][0] = tmpX;
            board[i][1] = tmpY;
        }

        // dp[i][j] = i번째 배달 위치에서 (중앙 , 하 , 상 , 우 , 좌)에 대한 최소 거리
        long[][] dp = new long[n + 1][5];

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 5; j++) {
                dp[i][j] = MAX;
            }
        }

        for (int i = 0; i < 5; i++) {

            int nx = board[1][0] + dx[i];
            int ny = board[1][1] + dy[i];

            if (outOfRange(nx, ny))
                continue;

            dp[1][i] = calDis(sx, sy, nx, ny); // 출발지에서 첫 좌표까지

        }


        for (int i = 2; i <= n; i++) {

            int curX = board[i][0];
            int curY = board[i][1];

            for (int j = 0; j < 5; j++) {

                int nX = curX + dx[j];
                int nY = curY + dy[j]; // i번째 위치의 중앙 , 하 , 상 , 우 , 좌 위치

                if (outOfRange(nX, nY))
                    continue; // 범위를 벗어난 경우

                long min = MAX;

                for (int k = 0; k < 5; k++) {
                    if (dp[i - 1][k] == MAX)
                        continue; // 이전에 해당 지점에 도착하지 못한경우

                    int pastX = board[i - 1][0] + dx[k];
                    int pastY = board[i - 1][1] + dy[k]; // 이전 좌표

                    if (outOfRange(pastX, pastY))
                        continue;

                    min = Math.min(min, dp[i - 1][k] + calDis(pastX, pastY, nX, nY));
                }

                dp[i][j] = min;

            }
        }

        long result = dp[n][0];

        for (int i = 1; i < 5; i++) {
            result = Math.min(result, dp[n][i]);
        }

        System.out.println(result);

        br.close();
    }

    // 좌표계의 범위는 0부터 100_000까지이다. (구간을 벗어난 경우 처리)
    static boolean outOfRange(int nx, int ny) {
        if (nx < 0 || nx > 100_000 || ny < 0 || ny > 100_000)
            return true;

        return false;
    }

    // 거리 공식 : 맨허튼 거리 공식 ( | x1 - x2 | + | y1 - y2 | )
    static long calDis(int sx, int sy, int lx, int ly) {
        return Math.abs(sx - lx) + Math.abs(sy - ly);
    }
}