[알고리즘] Java / 백준 / 진우의 달 여행 (Large) / 17485

[알고리즘] Java / 백준 / 진우의 달 여행 (Large) / 17485

문제

문제 링크

접근 방식

• 우주선이 연속으로 같은 방향을 가면 안되기 때문에 각각의 2차원 배열에 각 방향을 의미하는 3 크기의 배열을 넣는다 ( 0 : 왼쪽에서 내려옴, 1 : 가운데서 내려옴, 2 : 오른쪽에서 내려옴 )
• 이 때 이 배열 값의 의미는 각각 이전 방향에서 온 경로의 연료합 중 가장 적은 연료합을 뜻한다
• 즉 dp[i][j][k] 는 i-1행에서 k방향으로 온 연료합 중 가장 적은 연료합에 현재 i행 j열의 연료를 더한 값이다
• 예를 들어 dp[i][j][0]을 구하기 위해서는 dp[i-1][j-1] 중에서 k가 0이 아닌 1, 2의 값 ( 같은 방향이 아닌 값) 들 중 적은 값을 구한 후 현재 위치의 연료를 더한다

// 점화식
dp[i][j][0] = min(dp[i-1][j-1][!0]) + i,j 연료값
dp[i][j][1] = min(dp[i-1][j][!1]) + i,j 연료값
dp[i][j][2] = min(dp[i-1][j+1][!2]) + i,j 연료값

• 추가로 가장 왼쪽일 때와 오른쪽일 때를 고려하고, 연료 배열의 끝이 아닌 달까지 도달해야 한다

코드

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

public class Main_17485 {

	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[][] space = new int[N][M];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				space[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		// 이차원 배열의 각각 위치에 이전에 온 방향을 설명하는 배열 추가 
		// ( 0: 왼쪽에서 내려옴, 1 : 바로 아래로, 2: 오른쪽에서 내려옴 )
		
		int [][][] dp = new int[N+1][M][3]; // N번째는 달
		
		for(int i=0;i<=N;i++) {
			for(int j=0;j<M;j++) {
				for(int k=0;k<3;k++) {
					dp[i][j][k] = Integer.MAX_VALUE;
				}
			}
		}
		
		for(int j=0;j<M;j++) {
			for(int k=0;k<3;k++) {
				dp[0][j][k] = space[0][j];
			}
		}
		
		for(int i=1;i<=N;i++) {
			for(int j=0;j<M;j++) {
				int min;
				// 이전 행에서 현재 행으로 가능한 경로 중 가장 연료소모가 적은 경로 선택
					
				min = Integer.MAX_VALUE;
				// 왼쪽에서 오는 경우
				if(j > 0) {
					for(int pre=0;pre<3;pre++) {
						if(pre!= 0) {
							min = Math.min(min, dp[i-1][j-1][pre]);
						}
					}
					if(i==N) dp[i][j][0] = min;
					else dp[i][j][0] = min + space[i][j];
				}
				
				
				min = Integer.MAX_VALUE;
				// 오른쪽에서 오는 경우
				if(j<M-1) {
					for(int pre=0;pre<3;pre++) {
						if(pre!=2) {
							min = Math.min(min,dp[i-1][j+1][pre]);
						}
					}
					if(i==N) dp[i][j][2] = min;
					else dp[i][j][2] = min + space[i][j];
				}
				
				
				min = Integer.MAX_VALUE;
				// 가운데에서 오는 경우
				for(int pre=0;pre<3;pre++) {
					if(pre != 1) {
						min = Math.min(min, dp[i-1][j][pre]);
					}
				}
				if(i==N) dp[i][j][1] = min;
				else dp[i][j][1] = min +  space[i][j];
			}
		}
		
		int energy = Integer.MAX_VALUE;
		for(int j=0;j<M;j++) {
			for(int k=0;k<3;k++) {
				if(dp[N][j][k] != 0 ) energy = Math.min(dp[N][j][k],energy);
			}
		}
		
		System.out.println(energy);
		
	}

}