[11060] 점프 점프

🔗 문제 링크

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

🔍 문제 설명

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

⚠️ 제한사항

• 첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다.

• 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

---

🗝 풀이 (언어 : Java)

BFS, DP 모두 풀이가 가능하다.

1. BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        br.close();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        bfs(arr);
    }

    private static void bfs(int[] arr) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.addLast(0);
        boolean[] visited = new boolean[arr.length];
        visited[0] = true;
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer idx = queue.pollFirst();
                if (idx == arr.length - 1) {
                    System.out.println(count);
                    return;
                }
                for (int j = 1; j <= arr[idx] && idx + j < arr.length; j++) {
                    if (!visited[idx + j]) {
                        queue.addLast(idx + j);
                        visited[idx + j] = true;
                    }
                }
            }
            count++;
        }
        System.out.println(-1);
    }

}

2. DP

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        br.close();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dp(arr);
    }

    private static void dp(int[] arr) {
        int[] countArr = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if (i == 0 || countArr[i] != 0) {
                for (int j = 1; j <= arr[i] && i + j < countArr.length; j++) {
                    if (countArr[i + j] == 0) {
                        countArr[i + j] = countArr[i] + 1;
                    }
                }
            }
        }
        int answer = (arr.length == 1 || countArr[countArr.length - 1] != 0) ? countArr[countArr.length - 1] : -1;
        System.out.println(answer);
    }

}