C#으로 배열 끝까지 도달하는 최소 점프 횟수 구하는 방법

최소 점프(Minimum Jumps) 문제란?

배열의 각 요소는 해당 위치에서 최대 '그 값'만큼 앞으로 점프할 수 있다는 의미를 가집니다. 이때 목표는 배열의 첫 번째 인덱스에서 마지막 인덱스까지 이동하는 데 필요한 최소 점프 횟수를 구하는 것입니다.

첫 번째 요소에서 출발하여 도달 가능한 모든 요소를 재귀적으로 탐색하면 답을 구할 수 있습니다. 즉, "첫 요소에서 끝까지 가는 최소 점프 수"는 "첫 요소에서 도달 가능한 각 요소에서 끝까지 가는 최소 점프 수 + 1" 중 가장 작은 값이 됩니다.

예를 들어 다음 배열을 살펴보겠습니다.

Array == {1, 3, 6, 3, 2, 3, 6, 8, 9, 5};

이 배열에서 필요한 점프 수는 4입니다. 최적 경로는 인덱스 기준으로 0 → 1 → 3 → 6 → 9 순서입니다.

예제 코드

using System;
namespace ConsoleApplication{
   public class Arrays{
      public int MinJumps(int[] arr, int l, int h){
         if (h == l)
            return 0;
         if (arr[l] == 0)
            return int.MaxValue;
         int min = int.MaxValue;
         for (int i = l + 1; i <= h && i <= l + arr[l]; i++){
            int jumps = MinJumps(arr, i, h);
            if (jumps != int.MaxValue && jumps + 1 < min)
               min = jumps + 1;
         }
         return min;
      }
   }
   class Program{
      static void Main(string[] args){
         Arrays a = new Arrays();
         int[] arrm = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };
         int n = arrm.Length;
         Console.Write(" Minimum number of jumps to reach end is " + a.MinJumps(arrm, 0, n - 1));
      }
   }
}

실행 결과

4

코드 동작 원리

• 기저 조건 1: 시작 위치(l)와 끝 위치(h)가 같다면 더 이상 점프할 필요가 없으므로 0을 반환합니다.
• 기저 조건 2: 현재 위치의 값이 0이라면 더 이상 앞으로 나아갈 수 없으므로, 도달 불가능을 의미하는 int.MaxValue를 반환합니다.
• 재귀 탐색: 현재 위치에서 점프 가능한 범위(l + 1부터 l + arr[l]까지)에 속한 모든 지점에 대해 재귀적으로 최소 점프 수를 구하고, 그 결과에 1을 더한 값들 중 최솟값을 반환합니다.

참고: 성능 개선

위 재귀 방식은 직관적이지만, 같은 하위 문제를 반복해서 계산하므로 시간 복잡도가 지수(exponential) 수준까지 증가할 수 있습니다. 배열의 크기가 크다면 메모이제이션(memoization) 또는 동적 계획법(DP)을 활용해 각 위치별 최소 점프 수를 한 번만 계산하도록 최적화하는 것이 좋습니다.