[백준] 17485. 진우의 달 여행(Java)

문제

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

 

풀이

시작 행(0)에서 종료 행(r-1)까지 가는데 최단 거리(가중치)를 구하는 문제입니다.

이전과 같은 방향으로 두번 연속 움직일 수 없는 조건을 고려해주면 되는 문제입니다.

 

실패 케이스

처음에는 2차원 int 배열로 현재까지 온 최소 가중치를 저장했습니다.

bfs 탐색에서는 직전 방향과 현재 방향과 동일한 경우를 제외하고

dp[nr][nc] > dp[r][c] + arr[nr][nc]인 케이스에 대해서 다음으로 이동하도록 구현했습니다.

 

하지만, 이렇게 구현하다보니

최소값이 저장된 dp배열에는 방향이 고려되지 않는 값이 저장되어 원하는 결과가 나오지 않았습니다.

 

이러한 점을 고려하여

3차원 int 배열을 활용하여 현재까지 최소 가중치를 저장하는 방식으로 진행했습니다.

3차원 int 배열에서의 값은 각각 행, 열, 이전에 움직인 방향(왼쪽: 0, 가운데: 1, 오른쪽: 2을 의미합니다.

 

1. dp의 값을 초기화 해줍니다.(행이 0인 값에 대해서는 arr[0][열]의 값, 이외는 모두 INF로 초기화)

2. 행의 1번째부터 탐색하면서 dp 값을 갱신합니다.

2-1. 열이 0일 경우

   2-1-1. 가운데에서 온 케이스(dp[i][j][1])를 오른쪽에서 온 값 + 현재 값(arr[i][j])으로 갱신해줍니다.

   2-1-2. 오른쪽에서 온 케이스(dp[i][j][1])를 (왼쪽에서 온 값, 가운데에서 온 값 중 작은 값)  + 현재 값(arr[i][j])으로 갱신해줍니다.

2.2 열이 1 ~ M-2인 경우

   2-2-1. 왼쪽에서 온 케이스를 갱신해줍니다.

   2-2-2. 가운데에서 온 케이스를 갱신해줍니다.

   2-2-3. 오른쪽에서 온 케이스를 갱신해줍니다.

2.3 열이 M-1인 경우

   2-3-1. 왼쪽에서 온 케이스를 갱신해줍니다.

   2-3-2. 가운데에서 온 케이스를 갱신해줍니다.

3. dp[N-1]행의 값들 중 가장 작은 값을 추출해줍니다.

 

코드

110,772 KB / 688 ms / 2833 B

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

public class Main {
    static int N, M;
    static int[][] arr;
    static int[][][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        dp = new int[N][M][3]; // 가로, 세로, 이전방향 => 이전위치와 방향에 따른 최솟값

        for(int i = 0 ; i < N ; i ++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < M ; j ++){
                arr[i][j] = Integer.parseInt(st.nextToken());

                Arrays.fill(dp[i][j], 1_000_100);
            }
        }

        for(int i = 0 ; i < M ; i ++){
            for(int j = 0 ; j < 3 ; j ++){
                dp[0][i][j] = arr[0][i]; // dp 초기값 저장
            }
        }

        // 왼쪽 0, 가운데 1, 오른쪽 2
        // 어느 방향에서 왔는지 && 그 방향에서 온 것들 중 최솟값 파악
        for(int i = 1 ; i < N ; i ++){ // 행
            for(int j = 0 ; j < M ; j ++){ // 열
                if(j == 0){ // 열이 0이라면 => 가운데, 오른쪽 에서 올 수 있음
                    // 가운데에서 온 케이스(오른쪽 값만 올 수 있음)
                    dp[i][j][1] = dp[i-1][j][2] + arr[i][j];
                    // 오른쪽에서 온 케이스(이전 최솟값에서 왼쪽과 가운데 값 중 최솟값)
                    dp[i][j][2] = Math.min(dp[i-1][j+1][1], dp[i-1][j+1][0]) + arr[i][j];
                }
                else if(j < M-1){ // 왼쪽, 가운데, 오른쪽에서 올 수 있음
                    // 오른쪽에서 온 케이스
                    dp[i][j][2] = Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][0]) + arr[i][j];
                    // 가운데에서 온 케이스
                    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + arr[i][j];
                    // 왼쪽에서 온 케이스
                    dp[i][j][0] = Math.min(dp[i - 1][j - 1][2], dp[i - 1][j - 1][1]) + arr[i][j];
                }
                else{ // 왼쪽, 가운데에서 올 수 있음
                    // 왼쪽에서 온 케이스
                    dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + arr[i][j];
                    // 가운데에서 온 케이스(왼쪽 값만 올 수 있음)
                    dp[i][j][1] = dp[i-1][j][0] + arr[i][j];
                }
            }
        }

        int ans = 1 << 30;
        for (int i = 0; i < M; i ++) {
            for (int j = 0; j < 3; j ++)
                ans = Math.min(ans, dp[N - 1][i][j]);
        }

        System.out.println(ans);
    }
}