[Algorithm] 진우의 달 여행

🍪 백준 17484번 – 진우의 달 여행 (Small)

🔗 진우듸 달 여행

---

📌 문제 설명

우주비행이 꿈이었던 진우는 달 여행에 필요한 자금을 마련하여, 지구에서 달로 가는 우주선을 타게 되었습니다.
지구와 달 사이 공간은 N×M 크기의 행렬로 표현되며, 각 칸의 값은 해당 공간을 지날 때 소모되는 연료량을 뜻합니다.
진우의 우주선은 매번 한 칸씩 왼쪽 아래(↙), 아래(↓), 오른쪽 아래(↘) 방향으로만 이동할 수 있으며, 같은 방향을 두 번 연속으로 선택할 수 없습니다.
진우는 첫째 줄(지구)의 아무 위치에서 출발하여 마지막 줄(달)의 아무 위치에 도착할 때까지, 사용한 연료의 총합을 최소화하려고 합니다.

목표: 달까지 필요한 연료의 최솟값을 구하라.

---

입력 & 출력

• 입력

  • 첫 줄에 두 정수 N, M (2 ≤ N, M ≤ 6)이 주어집니다.
  • 다음 N줄에 걸쳐 M개의 자연수(1~100)가 주어지며, i번째 줄의 j번째 수는 (i, j) 칸을 지날 때 드는 연료량입니다.

• 출력

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

✨ 예제 입력 1

6 4
5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

✨ 예제 출력 1

29

---

💡 문제 핵심

1. 이동 방향은 3가지(↙, ↓, ↘)
2. 같은 방향을 연속 선택 불가
3. 전체 경로 중 연료 합 최소화 → 동적 계획법(DP) 활용

---

🔍 풀이 아이디어 (DP)

• DP 정의

  • dp[i][j][d] := i번째 행 j번째 열에 d 방향으로 들어왔을 때의 최소 연료 합
  • 방향 d는
    • 0 = 왼쪽 아래(↙)
    • 1 = 아래(↓)
    • 2 = 오른쪽 아래(↘)

• 초기값

  • 첫째 행 i = 1에서는 출발 위치마다 연료만큼 dp[1][j][*] = cost[1][j] 로 설정

• 점화식

  // ↙ (0): 이전에는 ↓(1) 또는 ↘(2)만 가능
  dp[i][j][0] = Math.min(dp[i-1][j+1][1], dp[i-1][j+1][2]) + cost[i][j];
  
  // ↓ (1): 이전에는 ↙(0) 또는 ↘(2)만 가능
  dp[i][j][1] = Math.min(dp[i-1][j][0], dp[i-1][j][2]) + cost[i][j];
  
  // ↘ (2): 이전에는 ↙(0) 또는 ↓(1)만 가능
  dp[i][j][2] = Math.min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + cost[i][j];

• 경계 처리

  • 배열 크기를 (N+1)×(M+2)로 잡아, 경계를 벗어나는 인덱스는 INF로 설정해 자연스럽게 제외

• 정답

  • 마지막 행 i = N에서 min(dp[N][j][0], dp[N][j][1], dp[N][j][2]) (j = 1..M)

---

✅ 자바 코드

import java.io.*;
import java.util.*;

public class Main {
    static final int INF = 1_000_000_000;
    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[][] cost = new int[N+1][M+2];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][][] dp = new int[N+1][M+2][3];
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= M+1; j++)
                Arrays.fill(dp[i][j], INF);

        // 초기값 설정
        for (int j = 1; j <= M; j++) {
            for (int d = 0; d < 3; d++) {
                dp[1][j][d] = cost[1][j];
            }
        }

        // DP 수행
        for (int i = 2; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dp[i][j][0] = Math.min(dp[i-1][j+1][1], dp[i-1][j+1][2]) + cost[i][j];
                dp[i][j][1] = Math.min(dp[i-1][j][0], dp[i-1][j][2]) + cost[i][j];
                dp[i][j][2] = Math.min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + cost[i][j];
            }
        }

        // 결과 계산
        int ans = INF;
        for (int j = 1; j <= M; j++) {
            for (int d = 0; d < 3; d++) {
                ans = Math.min(ans, dp[N][j][d]);
            }
        }
        System.out.println(ans);
    }
}

---

🧠 배운 점

• 역시 점화식을 세운다는게 제일 어렵다는 것을 알게 되었습니다....