[Algorithm] 점프 점프 (백준 - 11060)

📋 문제

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

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

입력

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

출력

• 재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입출력 예

예제 입력	예제 출력
10 1 2 0 1 3 2 1 5 4 2	5

✏️ 풀이

이 문제는 풀이방법이 두 가지가 생각났다. 첫번째는 DP이고, 두 번째는 BFS이다. 나는 DP를 이용해서 풀었다.

 

문제 설명이 살짝 헷갈렸는데 다시 한번 읽어보니 이해가 잘 됬다.(확실하게 읽자!!) 헷갈렸던 점이 현재 위치에서 얼마나 점프를 할 수 있는가였다. 문제에 "재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다." 라는 지문이 있는데 이게 핵심 포인트였다. 만약 첫 번째 미로에 위치해 있다면 A 배열의 첫 번째 인덱스에 해당하는 수 이하만큼 점프할 수 있다.

 

DP 점화식은 다음과 같다.

DP[i] = i 번째 미로까지 도달할 수 있는 최소 점프 횟수

따라서 현재 위치에서 A 배열의 인덱스에 해당하는 수 이하만큼 반복문을 돌리며 최소값을 갱신시켜주면 된다. 처음 DP 배열의 각 요소는  최솟값을 찾아야 하기 때문에 Infinity로 초기화해줬다. 초기 위치(1번째)는 0으로 초기화했다.

 

만약 범위를 벗어난다면 커지는 값이기 때문에 break해서 더 이상 확인하지 않고 인덱스를 초과하지 않는다면 Math.min 메서드를 사용하여 갈 수 있는 위치의 점프 횟수값을 갱신했다.

 

마지막으로 제일 끝 위치(N)가 Infinity라면 갈 수 없는 상황이므로 -1을 출력하고 아니라면 DP[N]을 출력하며 문제를 해결했다.

⌨️ 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './testcase/11060.txt';

let input = fs.readFileSync(filePath).toString().trim().split('\n');

const N = +input[0];
const arr = input[1].split(' ').map(Number);

const dp = new Array(N + 1).fill(Infinity);
dp[1] = 0;

for (let pos = 1; pos <= N; pos++) {
  for (let dist = 1; dist <= arr[pos - 1]; dist++) {
    if (pos + dist > N) break;
    dp[pos + dist] = Math.min(dp[pos + dist], dp[pos] + 1);
  }
}

console.log(dp[N] !== Infinity ? dp[N] : -1);