C 프로그래밍으로 배열 끝까지 도달하는 최소 점프 횟수 구하기

문제 설명

음이 아닌 정수로 이루어진 배열이 주어지며, 각 원소는 해당 위치에서 앞으로 이동할 수 있는 최대 걸음 수를 나타냅니다. 포인터는 처음에 배열의 첫 번째 인덱스(0번 인덱스)에 위치하고, 목표는 최소한의 점프 횟수로 배열의 마지막 인덱스에 도달하는 것입니다. 만약 배열의 끝에 도달하는 것이 불가능하다면 최대 정수값(INT_MAX)을 출력해야 합니다.

단순 접근법(Naive Approach)

가장 기본적인 방법은 첫 번째 원소에서 시작하여, 그 원소에서 도달 가능한 모든 원소에 대해 재귀적으로 호출하는 것입니다. 즉, 시작점에서 끝까지 도달하는 최소 점프 횟수는 '시작점에서 도달 가능한 각 원소에서 끝까지 도달하는 데 필요한 최소 점프 횟수' 중 가장 작은 값으로 계산됩니다.

minJumps(start, end) = Min ( minJumps(k, end) )
for all k accessible from the start

동적 계획법(Dynamic Programming) 활용

여기서는 동적 계획법의 탑다운(Top-down) 방식을 사용합니다. 해시맵(Hashmap)을 이용해 부분 문제의 결과를 저장하고, 새로운 해답을 계산하기 전에 해당 부분 문제가 이미 해결되었는지 먼저 확인합니다. 이미 해결된 부분 문제라면 저장된 결과를 그대로 재사용하여 불필요한 중복 계산을 줄입니다.

Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8}

동작 원리

첫 번째 원소는 1이므로 두 번째 위치로만 이동할 수 있습니다. 두 번째 원소는 2이므로 최대 2칸을 이동할 수 있으며, 값이 4인 위치 또는 값이 1인 위치로 갈 수 있습니다. 이 예제에서는 값이 4인 곳으로 이동한 뒤, 그곳에서 다시 1로 이동하는 식으로 경로가 이어져 최종적으로 마지막 인덱스에 도달하게 됩니다.

배열의 끝에 도달하기 위한 최소 점프 횟수를 구하는 동적 계획법의 시간 복잡도는 O(n²)이며, 공간 복잡도는 O(n)입니다.

C 언어 구현 예제

#include<stdio.h>
#include<limits.h>
int min_steps (int arr[], int n){
   int steps[n];
   int i, j;
   if (n == 0 || arr[0] == 0)
      return INT_MAX;
   steps[0] = 0;
   for (i = 1; i < n; i++){
      steps[i] = INT_MAX;
      for (j = 0; j < i; j++){
         if (i <= j + arr[j] && steps[j] != INT_MAX){
            steps[i] = (steps[i] < (steps[j] + 1)) ? steps[i] : steps[j] + 1;
            break;
         }
      }
   }
   return steps[n - 1];
}
int main (){
   int arr[100];
   int n;
   printf ("Enter size of the array:");
   scanf ("%d", &n);
   printf ("Enter elements in the array:");
   for (int i = 0; i < n; i++){
      scanf ("%d", &arr[i]);
   }
   printf ("Minimum number of steps : %d", min_steps (arr, n));
   return 0;
}

코드 설명

위 코드는 각 인덱스까지 도달하는 데 필요한 최소 점프 횟수를 순차적으로 계산합니다. 핵심 로직은 다음과 같습니다.

steps[0] = 0 : 시작 지점까지의 점프 횟수는 0입니다.
도달 가능 여부 판별 : 현재 위치 i가 이전 위치 j에서 점프 가능한 범위(i ≤ j + arr[j]) 안에 있는지 확인합니다.
최솟값 갱신 : 도달 가능한 경우, steps[j] + 1과 기존 steps[i]를 비교하여 더 작은 값으로 갱신합니다.
예외 처리 : 배열이 비어 있거나 첫 번째 원소가 0이라면 어디로도 이동할 수 없으므로 INT_MAX를 반환합니다.

실행 결과

Enter size of array : 7
Enter elements in the array :2 1 1 5 2 1 1
Minimum number of steps : 3

입력된 배열 {2, 1, 1, 5, 2, 1, 1}의 경우, 0번 인덱스 → 3번 인덱스 → 6번 인덱스 순으로 총 3번의 점프만으로 배열의 끝에 도달할 수 있습니다.