백준 17485[자바] java 진우의 달 여행

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

17485번: 진우의 달 여행 (Large)

▶문제

우주비행이 꿈이었던 진우는 음식점 '매일매일 싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주 사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.

[예시]

진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.

1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.

2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.

진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느 위치든 착륙하는 것이다.

최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최솟값을 계산해 주자.

---

▶입력

첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다.

다음 N 줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소 값은 100 이하의 자연수이다.

---

▶출력

달 여행에 필요한 최소 연료의 값을 출력한다.

---

▶해설

조건을 먼저 살펴보겠습니다.

1. 우주선은 7시 방향, 6시 방향, 5시 방향으로 이동 가능하다.

2. 우주선은 연속으로 같은 방향으로 가지 못한다.

 

한 점에 도달하는 방법은 범위에 따라 3가지로 나뉩니다.

1. m=0 -> 6시 방향 or 7시 방향

2. m= 1~m-2 -> 5시 방향, 6시 방향, 7시 방향

3. m= m-1 -> 6시 방향 or 7시 방향

 

따라서 한 점에서의 값과 어느 뱡향에서 왔는가를 담을 배열이 필요합니다.

dp [n][m][3]이라고 선언하겠습니다.

 

예시를 보겠습니다. (가장 좌측 위를 0,0  가장 우측 아래를 n-1, m-1), (7시 방향=2, 6시 방향=1, 5시 방향=0)

2 4

5 8 5 1

3 5 8 4

0,0인 5를 가는 방법은 2가지 입니다.

1열(6시 방향)과 2열(7시 방향)로 가는 방법 

1. 6시 방향에서 온 것은 5시 방향으로 밖에 갈 수 없습니다. 

2. 7시 방향에서 온 것은 5시 방향, 6시 방향 모두 갈 수 있습니다. 따라서 아래와 같은 점화식이 도출됩니다. 

dp[i][j][0] = Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + arr[i][j];
dp[i][j][1] = dp[i-1][j][0] + arr[i][j];

0,1인 8을 가는 방법은 3가지입니다.

1열(5시 방향), 2열(6시 방향), 3열(7시 방향) 가는 방법

dp[i][j][0] = Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + arr[i][j];
dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + arr[i][j];
dp[i][j][2] = Math.min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + arr[i][j];

0.3인 1을 가는 방법은 2가지입니다.

3열(5시 방향), 4열(6시 방향) 가능 방법

dp[i][j][1] = dp[i-1][j][2]+ arr[i][j];
dp[i][j][2] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0]) + arr[i][j];

주의 dp배열을 큰 값으로 채워놓지 않고 Math.min()을 사용한다면 0이 출력됩니다.

 

전체 코드

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

public class Main {

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

        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        int[][] arr = new int[n][m];
        int[][][] dp = new int[n][m][3];

        for (int i = 0; i < n; i++) {
            String[] s1 = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(s1[j]);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], 1000001);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 3; j++) {
                dp[0][i][j] = arr[0][i];
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (j == 0) {
                    dp[i][j][0] = Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + arr[i][j];
                    dp[i][j][1] = dp[i-1][j][0] + arr[i][j];
                } else if (j == m - 1) {
                    dp[i][j][1] = dp[i-1][j][2]+ arr[i][j];
                    dp[i][j][2] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0]) + arr[i][j];
                } else {
                    dp[i][j][0] = Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + arr[i][j];
                    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + arr[i][j];
                    dp[i][j][2] = Math.min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + arr[i][j];
                }
            }
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 3; j++) {
                result = Math.min(result, dp[n - 1][i][j]);
            }
        }
        System.out.println(result);
    }
}