게시물을 작성하면서 복습하는 문제를 선정하는 기준은<solved.ac 티어 실버 2 (Silver 2) 이상>입니다.

※ 본 사진과 해당 게시글 내용의 문제 모두 백준 : 온라인 저지[Baekjoon_OnlineJudge]사이트에서 발췌해왔습니다.

❓ 문제

백준 온라인 저지 (Baekjoon Online Judge) :11060 점프 점프

❗ 풀이

My Code

(1) DFS 활용

메모리 : 31300KB
시간 : 120ms

해당 풀이는
while문을 통해서

"""
오른쪽 끝 위치에서 시작 해서
매 위치마다 해당 위치부터 최대한 점프할 수 있을 만큼 점프해보는 방법
"""
을 활용한 것이다.

while문에서 idx가 1씩 계속 감소하는데
왼쪽으로 계속 옮겨가면서 비교하는 방식이고

now를 넘어가야만 now를 확실하게 올 수 있기 때문에
" now와 가장 멀리있는(최소 이동) now까지 점프가능한 위치를 찾기 "를 위해
now를 넘어가는 마지막 가장 오른쪽의 위치를 tmp로 업데이트하고

이 tmp를 다음 dfs 메서드의 인수로 넣어주는 것이다.

def find(now, idx, move):
    if now == 0:
        return move
    tmp = -1
    while idx != 0: # 0이 될 때까지
        idx -= 1
        if Block[idx] + idx < now: 
        # now보다 크거나 같다 == 도달할 수 있다.
        # 해당 위치(idx) + 점프 가능거리 (Block[idx]) >= now 
        # 여야지만 가능
            continue
        tmp = idx
        # 작아지기 직전값의 위치 (now와 가장 멀리 떨어져잇는 위치) 저장
    if tmp == -1:
        return -1
    move += 1 # 매 실행 : 1회 점프 → 누적시켜주기
    return find(tmp, tmp, move)

import sys
input = sys.stdin.readline
N = int(input())
Block = list(map(int, input().split()))

move = 0
print(find(N - 1, N - 1, move))

(2)BFS 활용

메모리 : 32420KB
시간 : 100ms

＊ 첫값을 시작값으로 bfs에 활용하기 때문에 숫자가 하나밖에 없을 경우엔 while q 내부의 코드에서 범위를 벗어나게 되는 호출이 발생
즉, N==1일 경우는 바로 끝내버려야한다.

이 BFS의 경우엔
가장 왼쪽부터 계산을 시작하는 방법이다.

최초로 도달한 값 == 최소 이동값이라는 점을 활용하기 위해
BFS만 사용하는 것이아닌
DP또한 같이 활용한다.

import sys
input = sys.stdin.readline
N = int(input())
Block = list(map(int, input().split()))
if N == 1:
    print(0)
    sys.exit()
from collections import deque
counting = [0]*N
q = deque()
q.append([0, Block[0]])
while q :
    now , jump = q.popleft()
    for i in range(1,jump+1): # for문을 돌려야 넘어가는 경우만 계산되는 실수를 방지할 수있다.
    # 최대 점프거리 이내 갈 수 있는 모든 위치 조회
        if now + i >= N or counting[now+i] != 0: # 이미 값이 있다는 것은 최솟값이 있다는 것
            continue
        counting[now+i] = counting[now] + 1
        q.append([now+i, Block[now+i]])
        
if counting[-1] : # 마지막 오른쪽 끝의 값 출력
    print(counting[-1])
else : # 0(False) 일 경우
    print(-1)