[백준] 진우의 달 여행 (Small) - Java

💡https://www.acmicpc.net/problem/17484

---

문제 설명

※ 문제에 대한 세부 내용은 위 링크를 통해 확인해주세요!

지구와 달 사이의 격자형 루트를 따라서 움직였을 때, 최소한의 연료를 쓰는 루트가는 경우 얼마의 연료가 소모되는지에 대해 알아야 하는 문제입니다.

일단 문제에서 볼 수 있는 부분이 입력 값 제한이 굉장히 작다는 생각이 들고 그래서 어떻게 풀어도 시간 제한으로 틀리는 경우는 드물 것 같다는 생각이 듭니다.

 

먼저, 제가 한 생각은 DP로 풀자는 생각이 들었습니다. 최소한의 연료 소모량을 구해야 한다는 부분과 이전까지 이동한 최소 연료 소모량을 이용해서 그 다음 위치에서의 최소 연료 소모량을 구할 수 있을 것 같다는 부분에서 DP를 생각했습니다.

방향이라는 제한이 없었으면 그냥 DP로 간단하게 풀 수 있겠지만 이전 방향은 사용하면 안됩니다. 이를 고려해서 점화식을 생각했습니다.

문제 풀이

< 점화식 >
dir = 현재 위치에서 어떤 방향의 이전 위치에서 값을 받을 지 정하기 위한 방향
n = 현재 위치의 행
m = 현재 위치의 열
v = 현재 위치까지 소모된 최소 연료량

∴ dp[dir][n][m] = min(dp[dir][n][m], dp[dir - 1][n - dx[dir]][m - dy[dir]], dp[dir + 1][n - dx[dir]][m - dy[dir]])
=> 이전 dir 방향의 위치에서 현재 위치로 이동했을 때 소모되는 최소 연료 소모량 

점화식이 설명해보겠습니다.

• 이전 dir 방향으로부터 현재 위치로 이동하기 위해선 이전 방향으로 갈 때의 방향은 dir이 아니어야 합니다.
  그렇기 때문에 dir -1, dir + 1로 다른 방향으로부터 이전 위치로 이동했을 때의 최소 연료 소모량을 표현한 것입니다.
• n - dx[dir], m - dy[dir]은 이전 위치를 나타내기 위해서 dx, dy를 활용해야겠다를 생각한 부분입니다.

이렇게 해서 마지막 위치에서의 최소 연료 소모량을 구하면 값을 도출할 수 있습니다.

문제 코드

import java.io.*;

public class Main {
    
    private static final int DIR = 3, MAX_SIZE = 6, EMPTY = 10000000;
    
    private static int n, m;
    
    private static int[] dx = {1, 1, 1};
    private static int[] dy = {0, 1, -1};
    private static int[][] space = new int[MAX_SIZE][MAX_SIZE];
    private static int[][][] dp = new int[DIR][MAX_SIZE][MAX_SIZE];
    
    public static void main(String args[]) throws IOException {
        initialize();
        simulate();
        System.out.println(getMinFuel());
    }
    
    private static int getMinFuel() {
        int result = EMPTY;
        for (int i = 0; i < DIR; i++) {
            for (int j = 0; j < m; j++) {
                result = Math.min(result, dp[i][n-1][j]);
            }
        }
        return result;
    }
    
    private static void simulate() {
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int d = 0; d < DIR; d++) {
                    int bx = i - dx[d];
                    int by = j - dy[d];
                    if (!inRange(bx, by)) continue;
                    
                    dp[d][i][j] = Math.min(dp[d][i][j], dp[(d + 1) % DIR][bx][by] + space[i][j]);
                    dp[d][i][j] = Math.min(dp[d][i][j], dp[(d + 2) % DIR][bx][by] + space[i][j]);
                }
                
            }
        }
    }

    
    private static boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }
    
    private static void initialize() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] tmp = br.readLine().split(" ");
        n = Integer.parseInt(tmp[0]);
        m = Integer.parseInt(tmp[1]);
        
        for (int i = 0; i < n; i++) {
            tmp = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                space[i][j] = Integer.parseInt(tmp[j]);
            }
        }
        
        for (int d = 0; d < DIR; d++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (i == 0) {
                        dp[d][i][j] = space[i][j];
                        continue;
                    }
                    dp[d][i][j] = EMPTY;
                }
            }
        }
    }
}

---

마무리

오랜만에 DP 문제를 풀었는데 난이도가 실버 3이지만 오랜 시간이 걸렸습니다,,,
계속 점화식을 제대로 도출하지 않고 이런 느낌으로 풀면 될꺼 같은데 하면서 풀어보다가 문제가 점점 더 헷갈리더라구요. 역시 처음부터 점화식을 제대로 도출하고 문제를 푸는게 가장 빠른 길인걸 느꼈습니다. 그래야 머리 속에 어떻게 답이 도출되는지 과정이 그려져서 좋은 것 같습니다.