백준 11060 - 점프 점프 (자바 - DP)

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

11060번: 점프 점프

 

* 문제 요약

재환이가 1 x N 크기의 미로에 갇혀있다. 미로는 1 x 1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여있다.

i번째 칸에 쓰여있는 수를 Ai 라고 했을 때, 재환이는 Ai 이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다.

예를 들어, 3번째 칸에 쓰여있는 수가 3 이면 재환이는 4,5,6번 칸 중 하나로 점프할 수 있다.

 

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 하낟. 이때, 최소 몇 번의 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오.

만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1 을 출력한다.

 

* 입력

첫째 줄에 N (1 <= N <= 1,000) 이 주어진다. 둘째 줄에는 Ai (0 <= Ai < 100) 가 주어진다.

 

* 출력

재환이가 최소 몇 번의 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다.

만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1 을 출력한다.

 

* 예시

 

* 해결 과정

그래프 문제를 풀기 위해 그래프 태그에 있는 문제를 풀려고 했으나 정작 DP 로 푸는게 더 쉬웠던 문제

 

미로의 가장 왼쪽에서 부터 가장 오른쪽으로 갈 때 뛰어야 하는 최소 점프 횟수를 구해야 한다.

만약 가장 오른쪽 끝으로 갈 방법이 없다면 -1을 출력한다.

mazeDP 배열을 만들어서 미로의 각 칸으로 가는데 필요한 최소 점프 횟수를 DP 알고리즘을 이용해 구하는 방식으로 문제를 풀었다.

 

우선 mazeDP 배열에서 첫 번째 칸(시작 지점) 만 0으로 초기화 해주고 나머지 칸들은 모두 int 타입의 최대값으로 초기화 해주었다.(각 칸으로 가는데 피룡한 최소 점프 횟수를 구해주기 위해)

그 뒤 input 배열을 통해 입력받은 미로 속 각 칸에 적혀있는 번호 배열을 처음부터 끝까지 탐색하되 다음과 같이 로직을 수행하였다.

1. number 변수에 현재 input 배열에 적혀있는 값을 int 타입으로 변환시켜 준 다음 저장한다.

2. 현재 탐색중인 칸의 오른쪽에 있는 칸으로 가는데 필요한 최소 점프횟수를 구해야하기 때문에 내부에 반복문을 하나 더 만들고, 해당 반복문은 i + 1 번째 (현재 탐색위치 바로 오른쪽) 부터 i + number (현재 위치에 적혀있는 번호만큼 오른쪽으로 떨어져 있는 칸까지) 로직을 수행하게끔 만들었다.

3. 내부 반복문에서는 현재 index 가 mazeDP 배열의 길이보다 작으면서, 현재 탐색중인 위치 i 의 값이 int 타입의 최대값이 아닌 경우. 즉, 현재 탐색중인 위치가 앞선 칸에서 점프를 통해 올 수 있는 곳인 경우(만약 현재 탐색중인 위치 mazeDP[i] 의 값이 int 타입 최대값이라면 앞선 칸에 적혀있는 번호만큼 점프를 해도 현재 탐색중인 위치에 도착할 수 없다는 뜻이다.)

현재 mazeDP 배열의 index 번째 위치의 값을 기존의 값(앞전에 이미 한번 도착한 적이 있는 경우) 과 현재 탐색중인 i 번째 위치에 도착하는데 필요한 점프 횟수 + 1 한 값을 비교하여 더 작은 값으로 저장해준다.

4. 반복문이 모두 끝나고 난 후 mazeDP 배열의 마지막 값이 int 타입의 최대값이 아닌 경우 mazeDP 배열의 마지막 값을 출력해주고, 그렇지 않은 경우 -1 을 출력시켜준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int nodeCount = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] mazeDP = new int[nodeCount];
        for (int i = 1; i < mazeDP.length; i++) {
            mazeDP[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < input.length; i++) {
            // 현재 미로 칸에 적혀있는 번호
            int number = Integer.parseInt(input[i]);

            for (int index = i + 1; index <= i + number; index++) {
                if (index < mazeDP.length && mazeDP[i] != Integer.MAX_VALUE) {
                    mazeDP[index] = Math.min(mazeDP[index], mazeDP[i] + 1);
                }
            }
        }

        if (mazeDP[mazeDP.length - 1] != Integer.MAX_VALUE) {
            bw.write(mazeDP[mazeDP.length - 1] + "\n");
        } else {
            bw.write(-1 + "\n");
        }

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

 

앞전의 칸에 도착하는데 필요한 최소 점프횟수를 구한 다음, 그것을 이용하여 다음의 칸으로 이동하는데 필요한 최소 점프횟수를 구하는 등 메모이제이션 기법을 이용하여 최종적인 도착지까지 가는데 필요한 점프횟수를 구했으므로 DP 알고리즘 문제에 해당된다.