백준 11909 (배열 탈출) - java

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

11909번: 배열 탈출

 

문제

상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다.

배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1]에 가둬 버렸습니다! 최소한의 양심이 있던 승현이는 A[n][n]에 출구를 만들어 놓고 이 사실을 상수에게 알려줬습니다.

상수는 가능한 한 빨리 출구인 A[n][n]에 도달하고자 합니다. 상수가 A[i][j]에 있다고 가정했을 때, 상수는 최단 경로로 이동하기 위해 아래와 같은 조건을 만족하며 이동합니다.

1. 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
2. i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
3. 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
4. i=j=n인 경우 바로 출구로 갑니다.

러나 건너갈 때에도 제약이 따릅니다. 상수가 A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]를 만족해야 합니다. 상수는 왜인지 이런 조건을 만족하면서 이동할 수 없을 것 같았습니다. 다행히도, 승현이가 상수를 배열에 가둬버리기 전에, 상수는 배열의 각 원소에 버튼을 만들어 놓아서, 이 버튼을 누르면 해당 원소의 값이 1 증가하도록 했습니다. (물론 상수는 자신이 위치해 있는 원소의 버튼만 누를 수 있습니다.) 이 버튼 덕분에, 상수는 항상 배열을 탈출할 수 있습니다!

[그림 3] n=2라고 가정합시다. A[1][1]=5>A[1][2]=2이므로, 상수는 A[1][1]에서 A[1][2]로 건너갈 수 있습니다. 상수가 A[1][1]에서 A[2][1]로 건너가려면, A[1][1]에 있는 버튼을 두 번 눌러 A[1][1]의 값을 7로 만들면 됩니다.

하지만 버튼을 한 번 누르는 데에는 1원의 비용이 듭니다. 상수는 돈을 가능한 한 적게 들이면서 배열을 탈출하고자 합니다. 상수를 도와주세요.

 

유형 : DP

 

접근 방식

• DP[i][j] = (i,j) 좌표에 가장 적은 돈으로 도착한 경우
  • 오른쪽과 아래로 이동 가능하다면  반대로 특정 좌표를 기준으로는 왼쪽과 위를 검사하면 된다. (bottom up)
  • 해당 좌표들간의 차이가 나는 경우 지나온 좌표가 크다면 그냥 Min 값 계산
  • 더 크거나 같은 경우 버튼을 얼마나 누르는지 차이를 계산하여 갱신

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int[][] board;
    static int[][] dp;

    static int[] dx = {-1,0};
    static int[] dy = {0,-1};

    static boolean[][] v;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        board = new int[n+1][n+1];
        dp = new int[n+1][n+1];
        v = new boolean[n+1][n+1];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(bf.readLine(), " ");

            for(int j=1;j<=n;j++){
                board[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        dp[1][1] = 0;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                go(i,j);
            }
        }


        System.out.println(dp[n][n]);

        bf.close();
    }

    static void go(int curX,int curY){

        v[curX][curY] = true;

        for(int i=0;i<2;i++){
            int nx = curX + dx[i];
            int ny = curY + dy[i];

            if(isOut(nx,ny))
                continue; // 범위를 벗어난 경우

            if(board[curX][curY] < board[nx][ny]){
                dp[curX][curY] = Math.min(dp[curX][curY],dp[nx][ny]); // 값을 키우지 않고 이동 가능한 경우
            }else{
                int dif = Math.abs(board[curX][curY] - board[nx][ny]) + 1;
                dp[curX][curY] = Math.min(dp[curX][curY],dp[nx][ny] + dif);
                // 값을 키워야지만 이동 가능한 경우
            }
        }
    }

    static boolean isOut(int x,int y){
        if(x < 1 || x > n || y < 1 || y > n)
            return true;

        return false;
    }
}