[백준 11060번] 점프 점프

문제출처:

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

 

 

백준 11060번 문제는 "점프 점프"라는 문제로, 주어진 배열에서 최단 거리를 이동하여 마지막 칸에 도달하는 방법을 찾는 문제입니다. 이 문제를 해결하기 위해서는 동적 프로그래밍(DP) 접근법을 사용하였습니다. 아래에 문제 풀이 과정을 단계별로 자세히 설명하겠습니다.

문제 이해

주어진 배열에서 각 원소는 그 위치에서 최대 몇 칸을 점프할 수 있는지를 나타냅니다. 목표는 첫 번째 칸에서 시작하여 마지막 칸에 도달하는 최소 점프 횟수를 구하는 것입니다.

 

입력 및 출력 형식

• 입력: 첫 줄에 배열의 크기 N이 주어지고, 두 번째 줄에 N개의 정수가 주어집니다.
• 출력: 마지막 칸에 도달하기 위한 최소 점프 횟수를 출력합니다. 만약 도달할 수 없다면 -1을 출력합니다.

 

왜 동적 프로그래밍을 사용해야 하는가?

1. 최적 부분 구조: 문제를 작은 문제로 나눌 수 있고, 작은 문제의 최적해를 이용하여 큰 문제의 최적해를 구할 수 있습니다. 이 문제에서는 특정 위치에 도달하기 위한 최소 점프 횟수를 구할 때, 이전 위치들의 최소 점프 횟수를 사용하여 계산할 수 있습니다.
2. 중복된 부분 문제: 여러 경로를 통해 같은 위치에 도달할 수 있으며, 각 경로마다 최소 점프 횟수를 계산해야 합니다. 이를 단순히 재귀적으로 풀면 동일한 부분 문제를 여러 번 계산하게 되어 비효율적입니다. DP는 이러한 중복 계산을 피하고, 이미 계산된 값을 재사용합니다.

 

DP를 사용해야 한다고 판단한 이유

1. 최소 점프 횟수 계산: 각 위치에 도달하는 최소 점프 횟수를 구하는 문제는 이전 위치의 결과를 기반으로 현재 위치의 결과를 도출하는 전형적인 DP 문제입니다. 특정 위치에 도달하는 최소 점프 횟수를 효율적으로 계산하기 위해서는 이전 위치의 정보를 저장하고 재사용할 필요가 있습니다.
2. 문제의 특성 분석:
   • 문제에서 주어진 배열의 각 원소는 해당 위치에서 점프할 수 있는 최대 칸 수를 나타냅니다. 즉, 현재 위치에서 점프 가능한 모든 위치를 고려해야 합니다.
   • 이때, 점프 가능한 모든 위치에 대해 최소 점프 횟수를 계산하여 업데이트해야 하므로, 이 과정에서 중복 계산이 발생할 수 있습니다. 이를 효율적으로 처리하기 위해 DP가 필요합니다.

 

DP 문제 해결 전략

1. 초기화: 첫 번째 위치의 점프 횟수를 0으로 설정하고, 나머지 위치의 점프 횟수는 무한대로 설정합니다. 이는 첫 번째 위치에서 시작하여 최소 점프 횟수를 계산하는 기반이 됩니다.
2. 점프 가능 범위 탐색: 각 위치에서 점프할 수 있는 모든 위치를 탐색하며, 해당 위치의 최소 점프 횟수를 업데이트합니다. 이때, 이미 계산된 최소 점프 횟수를 활용하여 중복 계산을 피합니다.
3. 결과 도출: 마지막 위치에 도달하기 위한 최소 점프 횟수를 확인하고, 도달할 수 없는 경우를 처리합니다.

 

문제 풀이 과정

1. 초기화: 각 칸에 도달하기 위한 최소 점프 횟수를 저장할 배열을 만듭니다. 초기값은 무한대로 설정합니다.
2. 첫 번째 칸 설정: 첫 번째 칸에서 시작하므로 첫 번째 칸의 점프 횟수는 0입니다.
3. 점프 시뮬레이션: 각 칸에서 점프할 수 있는 최대 범위 내의 칸들을 업데이트합니다.
4. 결과 출력: 마지막 칸의 값이 초기값이면 도달 불가하므로 -1을, 그렇지 않으면 최소 점프 횟수를 출력합니다.

 

def min_jumps(arr):
    N = len(arr)
    # 초기화: 무한대로 설정
    dp = [float('inf')] * N
    dp[0] = 0  # 첫 번째 칸은 점프 횟수 0

 

• N = len(arr): 배열의 길이 N을 계산합니다.
• dp = [float('inf')] * N: 길이가 N인 dp 배열을 생성하고, 모든 값을 무한대로 초기화합니다. 이 초기화는 도달할 수 없는 위치를 나타내기 위해 사용됩니다. 무한대로 설정하면 나중에 최솟값을 계산할 때 유리합니다.
• dp [0] = 0: 첫 번째 칸에서 시작하므로 첫 번째 칸의 점프 횟수는 0입니다.

 

    for i in range(N):
        for j in range(1, arr[i] + 1):
            if i + j < N:
                dp[i + j] = min(dp[i + j], dp[i] + 1)

 

• for i in range(N): 배열의 각 칸을 순회합니다. i는 현재 위치를 나타냅니다.
• for j in range(1, arr [i] + 1): 현재 위치 i에서 점프할 수 있는 최대 범위 내의 모든 칸을 순회합니다. j는 점프하는 칸 수를 나타냅니다. arr [i]는 위치 i에서 최대 몇 칸을 점프할 수 있는지를 나타내므로, 1부터 arr [i]까지 순회합니다.
• if i + j < N: 점프한 위치 i + j가 배열의 범위를 벗어나지 않는지 확인합니다. 배열의 인덱스는 0부터 N-1까지이므로, i + j가 N보다 작은 경우에만 업데이트를 수행합니다.
• dp[i + j] = min(dp [i + j], dp [i] + 1): 점프한 위치 i + j의 최소 점프 횟수를 업데이트합니다. dp [i + j]는 현재 위치에서 점프하지 않고 도달한 경우의 점프 횟수이고, dp [i] + 1은 현재 위치에서 점프하여 도달한 경우의 점프 횟수입니다. 두 값 중 더 작은 값을 선택하여 dp [i + j]에 저장합니다.

 

    return -1 if dp[-1] == float('inf') else dp[-1]

 

• dp [-1]: dp 배열의 마지막 원소는 마지막 칸에 도달하기 위한 최소 점프 횟수를 나타냅니다.
• if dp[-1]dp [-1] == float('inf'): 만약 dp [-1]이 여전히 무한대라면, 이는 마지막 칸에 도달할 수 없음을 의미합니다.
• return -1 if dp[-1]dp [-1] == float('inf') else dp [-1]: 마지막 칸에 도달할 수 없으면 -1을 반환하고, 도달할 수 있으면 최소 점프 횟수를 반환합니다.

 

 

 

 

전체 코드:

https://github.com/jinjung0101/ALGORI/blob/main/%ED%85%8C%EC%8A%A4%ED%8A%B8%EC%97%B0%EC%8A%B5/%EB%B0%B1%EC%A4%80/11060.py