[LEETCODE 150] - 45 Jump Game II

LeetCode의 45번 문제인  "Jump Game II" 문제이다.

한번 점프할때 도달 가능한 구간을 레벨 단위로 넓혀가는 방식으로

 

이문제의 알고리즘인 BFS 방식을 이용해서 풀어봤다.

 

문제아이디어

nums[i]는 i에서 최대 점프 거리.

0번에서 시작해서 마지막 인덱스 까지 가는 최소 점프 횟수를 구하는 문제.

 

• l , r "현재 점프 횟수(res)"로 도달 가능한 인덱스 범위를 의미함.
• 어떤칸에서 점프하든, 다음 점프에서 도달 가능한 가장 먼곳을 계산해서 구간을 확장함
• 레벨(res)에서 방문 가능한 노드 범위가 [l,r]일때 다음레벨 (res+1)에서 방문 가능한 최대 범위가 farthest

 

정답코드 (Python)

class Solution:
    def jump(self, nums: List[int]) -> int:
        res = 0
        l = r = 0
        
        while r < len(nums) - 1:
            farthest = 0
            for i in range(l, r + 1):
                farthest = max(farthest, i + nums[i])
            l = r + 1
            r = farthest
            res += 1
        return res

 

풀이 해석

1. res : 점프 횟수 , 시작점 0에서 출발하므로 현재 "0번 인덱스만 도달 가능" → [l, r] = [0, 0]

class Solution:
    def jump(self, nums: List[int]) -> int:
    	res = 0
        l = r = 0

2. 아직 마지막 인덱스에 도달가능한 범위에 들어가지 않았다면 r이 마지막 인덱스 이상이면 끝

- 현재 범위 [l, r] 안의 모든 위치 i를 확인하면서

- 다음 점프로 도달 가능한 최대 인덱스 i + nums[i]를 계산

- 그중 최댓값이 farthest (이번 점프(res)로 도달 가능한 모든 발판을 고려했을 때, 한 번 더 점프하면 어디까지 갈수 있나?)

while r < len(nums) - 1:
	farthest = 0
    for i in range(l, r + 1):
    	farthest = max(farthest, i + nums[i])

3. 점프를 한번 수행했다고 보고(res += 1)

- 다음 레벨(다음 점프)에서 도달 가능한 구간을 갱신:

- 새 구간의 시작 l은 이전 구간 끝 다음 칸 r+1

- 새 구간의 끝 r은 방금 구한 farthest

- 마지막 인덱스가 현재 도달 범위 안으로 들어오면 종료 → 최소 점프 횟수 반환

l = r + 1
r = farthest
res += 1

return res

 

예시로 따라가보기

nums = [2,3,1,1,4]

초기: res=0, l=0, r=0

1회차 (현재 구간 [0,0])

• i=0 → farthest = max(0, 0+2)=2
• 갱신: l=1, r=2, res=1

2회차 (현재 구간 [1,2])

• i=1 → 1+3=4 → farthest=4
• i=2 → 2+1=3 → farthest=4
• 갱신: l=3, r=4, res=2
• r=4는 last index(4) 도달 → 종료

정답 : 2