[Baekjoon] 17484 진우의 달 여행 (Small/Big) (Java)

문제링크

Small: https://www.acmicpc.net/problem/17484
Big: https://www.acmicpc.net/problem/17485

문제

각 칸마다 지나가는데 소요되는 비용이 주어진다.
최소 비용으로 제일 위에서 아래칸에 도달하는 비용을 구하는 문제이다.
조건은 다음과 같다.
1. 직선 대각선 방향 한 칸씩 이동 가능하다.
2. 연속으로 같은 방향을 선택할 수 없다.

풀이

Small 문제인 것으로 봐서 Large 문제도 있겠다고 생각할 수 있다.

그리고 Small이므로 N,M <=6 이고 어떻게 풀더라도 논리만 맞으면 통과할 수 있음을 예상할 수 있다.

BFS를 통한 풀이와 DP를 이용한 풀이가 떠올랐는데, 이왕 푸는 거 Large도 통과할 수 있는 DP풀이를 도전해봤다.

각 칸이 담고 있는 정보는 다음과 같다.
DP[i][j][0] : 해당 칸을 우측 대각선으로 들어오는 경우
DP[i][j][1] : 해당 칸을 직진으로 들어오는 경우
DP[i][j][2] : 해당 칸을 좌측 대각선으로 들어오는 경우

여기서 한가지 경우에 대해 정보를 얻기 위해서는 바로 전 줄에 있는 정보들을 확인해야한다.

예를 들면 DP[i][j][0] 은 DP[i-1][x][y]를 확인해야한다. 이때 이미 들어오는 방향은 결정됐으므로 x값을 결정할 수 있다. 여기서 연속으로 같은 방향을 선택할 수 없다는 조건을 충족하기 위해 y는 0이 아닌 값만 확인한다.

if(p==0) tmp = Integer.min(tmp, Integer.min(Dp[i-1][j-1][1], Dp[i-1][j-1][2]));

이렇게 점화식을 각각의 경우에 대해 작성한 후 마지막 줄의 값을 비교해 최소값을 출력한다.

코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N, M, tmp, answer = Integer.MAX_VALUE;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int[][] Map = new int[N+1][M+1];
        int[][][] Dp = new int[N+1][M+2][3];

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

        for(int i=1; i<=N; i++){
            for(int j=0; j<=M+1; j++){
                for(int k=0; k<3; k++) {
                    if(i==1 &&j>=1&&j<=M) Dp[i][j][k] = Map[i][j];
                    else Dp[i][j][k] = 10101010;
                }
            }
        }


        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){

                for(int p=0; p<3; p++){
                    tmp = 10101010;
                    if(p==0) tmp = Integer.min(tmp, Integer.min(Dp[i-1][j-1][1], Dp[i-1][j-1][2]));
                    else if(p==1) tmp = Integer.min(tmp, Integer.min(Dp[i-1][j][0], Dp[i-1][j][2]));
                    else tmp = Integer.min(tmp, Integer.min(Dp[i-1][j+1][0], Dp[i-1][j+1][1]));

                    Dp[i][j][p] = tmp + Map[i][j];
                }
            }
        }

        for(int i=1; i<=M; i++){
            for(int j=0; j<3; j++) answer = Integer.min(answer, Dp[N][i][j]);
        }

        System.out.println(answer);
    }
}

tmp변수를 이용해서 각 경우의 최소값을 찾아냈는데, tmp의 초기화를 for문 밖에서 진행하는 바람에 한참동안 코드를 들여봐야했다. 변수를 매번 초기화하는 경우 적절한 위치인지 잘 확인해야겠다.