[Boj_17485] 진우의 달 여행 (Large)

📎 문제 링크

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

 

▸ 문제

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

[예시]

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

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

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

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

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

 

▸ 입력

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

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

 

▸ 출력

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

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 5
• 🔔  문제 유형 : 다이나믹 프로그래밍
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 이전 이동 방향을 고려하면서 최솟값을 갱신해 나가야 하므로 3차원 DP로 해결할 수 있다.

int[][][] dp = new int[n][m][3]; // d 방향으로 온 (i, j) 위치

 

1️⃣ 첫 번째 열 (j == 0)

(i, 0) 좌표에 도달하는 경우

• 0번 방향(↙)으로 도착한 경우: 직전은 1번(↓) 또는 2번(↘)만 가능
• 1번 방향(↓)으로 도착한 경우: 직전은 0번(↙)만 가능

이 문제는 같은 방향으로 두 번 연속 이동할 수 없기 때문에, 가능한 이전 방향을 고려해 DP를 갱신해야 한다.

 

그림으로 나타내면 아래와 같다.

 

📌 코드 예시

if (j == 0) {
    // (i, j)가 0번 방향으로 왔다면: 이전 위치는 (i-1, j+1)에서 1 or 2 방향으로 왔어야 함
    dp[i][j][0] = Math.min(dp[i-1][j+1][1], dp[i-1][j+1][2]) + map[i][j];
    // (i, j)가 1번 방향으로 왔다면: 이전 위치는 (i-1, j)에서 0번 방향만 가능
    dp[i][j][1] = dp[i-1][j][0] + map[i][j];
}

 

2️⃣ 마지막 열 (j == m-1)

(i, m-1) 좌표에 도달하는 경우

• 1번 방향(↓)으로 도착한 경우: 직전은 2번 방향(↘)만 가능
• 2번 방향(↘)으로 도착한 경우: 직전은 0번(↙) 또는 1번(↓) 방향만 가능

오른쪽 끝 열에서는 0번 방향(↙)은 불가능하기 때문에, 가능한 이전 방향을 고려해 DP를 갱신해야 한다.

 

그림으로 나타내면 아래와 같다.

 

📌 코드 예시

if (j == m - 1) {
    // (i, j)가 1번 방향(↓)으로 왔다면: 이전 위치는 (i-1, j)에서 2번 방향만 가능
    dp[i][j][1] = dp[i - 1][j][2] + map[i][j];
    // (i, j)가 2번 방향(↘)으로 왔다면: 이전 위치는 (i-1, j-1)에서 0번 또는 1번 방향 가능
    dp[i][j][2] = Math.min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + map[i][j];
}

 

3️⃣ 중간 열 (1 ≤ j ≤ m - 2)

(i, j) 좌표에 도달하는 경우, 세 가지 방향 모두에서 이동이 가능하다.

다만, 같은 방향으로 두 번 연속 이동할 수 없기 때문에, 각 방향에 대해 직전 방향을 제외한 나머지 방향들 중에서 최솟값을 선택해 DP를 갱신한다.

 

💡 예시 설명

예를 들어 현재 위치가 (i, j)라고 하면:

• 0번 방향(↙)으로 온 경우: 직전에는 1번(↓) 또는 2번(↘)만 가능
• 1번 방향(↓)으로 온 경우: 직전에는 0번(↙) 또는 2번(↘)만 가능
• 2번 방향(↘)으로 온 경우: 직전에는 0번(↙) 또는 1번(↓)만 가능

 

그림으로 나타내면 아래와 같다.

 

📌 코드 예시

if (j > 0 && j < m - 1) {
    // (i, j)가 0번 방향(↙)으로 왔다면: 이전 위치는 (i-1, j+1)에서 1번 또는 2번 방향 가능
    dp[i][j][0] = Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + map[i][j];
    // (i, j)가 1번 방향(↓)으로 왔다면: 이전 위치는 (i-1, j)에서 0번 또는 2번 방향 가능
    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + map[i][j];
    // (i, j)가 2번 방향(↘)으로 왔다면: 이전 위치는 (i-1, j-1)에서 0번 또는 1번 방향 가능
    dp[i][j][2] = Math.min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + map[i][j];
}

 

마지막 행의 모든 열에서, 세 방향에 대한 최솟값을 찾으면 달 여행에 필요한 최소 연료의 값을 구할 수 있다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 코드

메모리 : 114760KB
시간 : 512ms

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 INF = 987654321;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] map = new int[n][m];
        int[][][] dp = new int[n][m][3]; // d 방향으로 온 (i, j) 위치
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                Arrays.fill(dp[i][j], INF);
            }
        }

        // 초기 설정
        for (int j = 0; j < m; j++) {
            dp[0][j][0] = map[0][j];
            dp[0][j][1] = map[0][j];
            dp[0][j][2] = map[0][j];
        }

        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]) + map[i][j];
                    dp[i][j][1] = dp[i-1][j][0] + map[i][j];
                } else if (j == m-1) {
                    dp[i][j][2] = Math.min(dp[i-1][j-1][1], dp[i-1][j-1][0]) + map[i][j];
                    dp[i][j][1] = dp[i-1][j][2] + map[i][j];
                } else {
                    dp[i][j][2] = Math.min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + map[i][j];
                    dp[i][j][1] = Math.min(dp[i-1][j][2], dp[i-1][j][0]) + map[i][j];
                    dp[i][j][0] = Math.min(dp[i-1][j+1][1], dp[i-1][j+1][2]) + map[i][j];
                }
            }
        }

        int min = INF;
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < 3; i++) {
                min = Math.min(min, dp[n-1][j][i]);
            }
        }

        System.out.println(min);

        br.close();
    }
}

 

dp를 끔찍이도 싫어하던 난데.. 요즘엔 흥미가 생겨 살짝 재밌게 느껴진다!
물론 다른 사람의 풀이를 참고해서 해결하는 경우가 많지만 열심히 풀다 보면 혼자 해결하는 날도 늘어나겠지...! 😜