BEAKJOON / 백준 - JAVA 17484번 진우의 달 여행 (Small)

2024.09.01기준 - 실버3

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 행렬이 주어질 때 제시된 조건에 맞게 움직이면서 가장 연료량을 적게 소모하여 도착하는 경우를 출력하는 문제입니다.

 

1. 먼저 입력받은 행렬을 2차원 배열에 저장을 해줍니다.

// 입력된 연료 소모량을 저장하는 배열
int[][] grid = new int[h][w];

// 입련된 연료 소모량을 먼저 배열에 저장합니다.
for (int i = 0; i < h; i++) {
    st = new StringTokenizer(br.readLine());

    for (int j = 0; j < w; j++) { 
        grid[i][j] = Integer.parseInt(st.nextToken());
    }
}

 

2. 움직일 수 있는 방향이 3방향이기 때문에 dp는 3차원 배열로 생성해줍니다. 

(모든 경우의 수를 계산해줍니다.)

// 현재 위치까지 가는데 소모되는 연료량을 저장하는 배열
int[][][] dp = new int[h][w][3];

 

3. dp 계산을 위해 우선적으로 첫 번째 줄 연료량을 먼저 입력해줍니다.

// dp계산을 위해 0줄을 먼저 dp에 입력
for (int i = 0; i < w; i++) {
    for (int j = 0; j < 3; j++) {
        dp[0][i][j] = grid[0][i];
    }
}

 

4. 그 외

같은 방향이 아닌 다른 방향으로 오는 연료량을 전부 다 계산하는 방식으로 접근합니다.

방향은 0 → 왼쪽, 1 → 가운데, 2 → 오른쪽으로 접근합니다.

 

if (j == 0) { // 맨 왼쪽은 왼쪽이 없기 때문에 왼쪽에서 오는 방향은 이 문제의 최댓값인 600이 넘는 수를 할당.
    dp[i][j][0] = 700;
    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + grid[i][j];
    dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + grid[i][j];
} else if (j == w - 1) { // 맨 오른쪽은 오른쪽이 없기 때문에 동일하게 600이 넘는 값을 할당.
    dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + grid[i][j];
    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + grid[i][j];
    dp[i][j][2] = 700;
}

여기서 주의할 점은 제일 왼쪽과 오른쪽은 전 인덱스에서 왼쪽과 오른쪽에서 올 수 없기 때문에 이 문제의 결과의 최대값인 600을 넘는 수를 임의로 할당을 해줍니다.

 

else {
    dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + grid[i][j];
    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + grid[i][j];
    dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + grid[i][j];
}

0이면 1, 2에서 1이면 0, 2에서 2면 0, 1에서 작은 값을 더 해 나가면서 dp를 계산해줍니다.

 

5. 저장된 dp에서 제일 마지막 줄에서 가장 작은 값을 출력해줍니다.

// 계산된 마지막 줄의 연료량 중 가장 작은 연료량을 출력
int min = 700; 
for (int i = 0; i < w; i++) {
    for (int j = 0; j < 3; j++) {
        min = Math.min(min, dp[h - 1][i][j]);
    }
}

 

 

 

코드

package Main;

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int h = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		
		// 입력된 연료 소모량을 저장하는 배열
		int[][] grid = new int[h][w];
		
		// 현재 위치까지 가는데 소모되는 연료량을 저장하는 배열
		int[][][] dp = new int[h][w][3];
		
		// 입련된 연료 소모량을 먼저 배열에 저장합니다.
		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < w; j++) { 
				grid[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// dp계산을 위해 0줄을 먼저 dp에 입력
		for (int i = 0; i < w; i++) {
			for (int j = 0; j < 3; j++) {
				dp[0][i][j] = grid[0][i];
			}
		}
		
		// dp 계산 시작.
		for (int i = 1; i < h; i++) {
			for (int j = 0; j < w; j++) {
				// 같은 방향이 아닌 다른 방향으로 오는 연료량들을 전부 다 계산하는 방식으로 접근.
				// 방향 : 0 → 왼쪽, 1 → 가운데, 2 → 오른쪽
				if (j == 0) { // 맨 왼쪽은 왼쪽이 없기 때문에 왼쪽에서 오는 방향은 이 문제의 최댓값인 600이 넘는 수를 할당.
					dp[i][j][0] = 700;
					dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + grid[i][j];
					dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + grid[i][j];
				} else if (j == w - 1) { // 맨 오른쪽은 오른쪽이 없기 때문에 동일하게 600이 넘는 값을 할당.
					dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + grid[i][j];
					dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + grid[i][j];
					dp[i][j][2] = 700;
				} else {
					dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + grid[i][j];
					dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + grid[i][j];
					dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + grid[i][j];
				}
			}
		}
		
		// 계산된 마지막 줄의 연료량 중 가장 작은 연료량을 출력
		int min = 700; 
		for (int i = 0; i < w; i++) {
			for (int j = 0; j < 3; j++) {
				min = Math.min(min, dp[h - 1][i][j]);
			}
		}
		
		bw.write(Integer.toString(min));
		bw.flush();
		bw.close();
		br.close();
	}
}