[BOJ] 17485 진우의 달 여행 (Large) - Java

✨ DP

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

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

---

📍 고려해야할 점 

• 왼쪽 대각선, 아래, 오른쪽 대각선 3가지 방향으로 이동한다.
• ✨✨ 같은 방향으로 두 번 연속으로 움직일 수 없다. ✨✨

 

 

🕹️ 문제 풀이 

• 현재 위치를 기준으로 그 전 단계에 사용했던 연료의 양을 계속 알고 있어야 한다.
• 그 전 단계에 사용했던 연료의 양과 현재 위치에 있는 연료의 양의 합을 구해서 최소의 연료를 사용할 수 있는 경우를 dp배열에 저장한다.
  
  • 다만, 같은 방향으로 두 번 연속으로 움직일 수 없기 때문에 어떤 방향으로 이동했는지에 대한 정보 또한 저장하고 있어야 한다. 
    👉 dp 배열을 3차원 배열로 생성하여 계산하면 효율적으로 처리 가능 

✨ 점화식
dir : 3가지 방향 번호 
N : 현재 위치의 행 번호
M : 현재 위치의 열 번호

∴ 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+1, dir-1 으로만 이동 가능하므로 두가지 방향에 대해 비교한다. 

 

 

👩‍💻 문제 코드 

 

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

public class BOJ_17484_진우의달여행 {
	
	static final int DIR = 3;
	static int[] dx = {-1, -1, -1};
	static int[] dy = {-1, 0, 1};
	
	static int N, M;
	static int[][] fuel;
	static int[][][] dp;
	
	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 nx = i + dx[d];
                    int ny = j + dy[d];
                    if (!isValid(nx, ny)) continue;

                    dp[d][i][j] = Math.min(dp[d][i][j], dp[(d + 1) % DIR][nx][ny] + fuel[i][j]);
                    dp[d][i][j] = Math.min(dp[d][i][j], dp[(d + 2) % DIR][nx][ny] + fuel[i][j]);
                }

            }
        }
    }
	
	static boolean isValid(int x, int y) {
		return x>=0 && y>=0 && x<N && y<M;
	}
	
	static int getMin() {
		int result = Integer.MAX_VALUE;
		
		for(int d=0; d<DIR; d++) {
			for(int i=0; i<M; i++) {
				result = Math.min(result, dp[d][N-1][i]);
			}
		}
		return result;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		fuel = new int[N][M];
		dp = new int[DIR][N][M];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				fuel[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// dp 초기화 
		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]=fuel[i][j];
						continue;
					}
					dp[d][i][j] = 10000000;
				}
			}
		}
		
		simulate();
		
		System.out.println(getMin());
	}
}

 

 

 

 

백준에서 문제 좀 풀려고 아무거나 선택했는데 최근에 코테에서 본 문제와 거의 흡사했다. (똑같다고 해도 무방..)

백준 문제를 많이 풀어야겠다는 것을 바로 체감할 수 있었다..