백준 - 11909 배열 탈출(Java)

 

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

11909번: 배열 탈출

 

DP 문제입니다.

N이 주어졌을 때, 2차원 배열 (1, 1)에서 특정 조건을 따르면서 (N, N)까지 가는  최소 경로를 구하는 문제입니다.

문제 조건은 백준 문제에 잘 적혀있으니 추가적인 설명은 하지 않겠습니다.

(문제 아래에 힌트가 있으니 문제가 이해가지 않으면 참고하시기 바랍니다.)

단, 주의해야 할 점은 현재 숫자가 이동 하려는 위치의 숫자보다 커야합니다.

(동일하면 움직일 수 없기 때문에 현재 숫자를 증가시켜야 합니다.)

 

반복문 두 개를 겹쳐 가로, 세로로 이동할 수 있는 위치를 판단해 이동시켰을 때의 최소를 갱신시키면 됩니다.

최소 갱신은 dp 배열에 저장합니다.

 

[구현 코드]

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

public class Main {
    private static int n;
    private static int[][] map, dp;

    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 stz;

        n = Integer.parseInt(br.readLine());

        map = new int[n + 1][n + 1];
        dp = new int[n + 1][n + 1];

        for (int i = 1; i < n + 1; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j < n + 1; j++) {
                map[i][j] = Integer.parseInt(stz.nextToken());
            }
        }

        dp[1][1] = 0;
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if (i == 1 && j == 1) continue;

                // 가로 위치 판단
                int c = map[i][j] - map[i][j - 1];
                // 세로 위치 판단
                int r = map[i][j] - map[i - 1][j];

                int a = 0;
                int b = 0;

                // 가로 비교
                if (map[i][j] < map[i][j - 1]) {
                    // 현재가 숫자가 더 크기 때문에 숫자 증강이 필요 없음 
                    a = dp[i][j - 1];
                } else {
                    // 현재 숫자가 더 작기 때문에 "차이+1" 만큼 숫자 증강
                    a = c + 1 + dp[i][j - 1];
                }

                // 세로 비교
                // 가로와 동일
                if (map[i][j] < map[i - 1][j]) {
                    b = dp[i - 1][j];
                } else {
                    b = r + 1 + dp[i - 1][j];
                }

                // 알고리즘상 배열 1번부터 시작하기 때문에 0번과 비교하지 않게 함
                // 배열 0번을 무한대로 초기화하면 이 코드는 필요 없음
                if(i == 1) b = 1_000_000;
                if(j == 1) a = 1_000_000;

                // 가로와 세로의 이동을 판단하여 최소의 값만 갱신함
                dp[i][j] = Math.min(a, b);
            }
        }

        bw.write(String.valueOf(dp[n][n]));

        bw.flush();
        bw.close();
        br.close();
    }
}