[백준] 11060번 - 점프 점프

야금야금 공부·2023년 5월 29일
0

백준

목록 보기
45/46

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

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 AiAi라고 했을 때, 재환이는 AiAi이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 AiAi (0 ≤ AiAi ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.



1. BFS 풀이

  1. 점프한 인덱스 idx와 점프 횟수 cnt에 넣어준다.

    큐의 초기값 : [0, 0]

  2. 큐 안에 값 idxcnt이 존재하면 꺼낸다.

    1. idx+1부터 idx+ jump[idx]까지 방문하지 않은 값이 있으면, cnt + 1과 점프한 위치 idx + i를 큐에 넣는다.
    2. 만약 idxjump 리스트의 가장 마지막에 도달했다면, cnt를 반환하고 멈춘다.
import sys
from collections import deque

input = sys.stdin.readline

# 1xN 크기 미로
n = int(input())
jump = list(map(int, input().split()))
visited = [False] * n


# jump[i]이하만큼 점프 가능
# 최소 몇번 점프를  해야하는 가

def minjump(idx, cnt):
    queue = deque()
    queue.append([idx, cnt])

    while queue:
        idx, cnt = queue.popleft()

        if idx == n - 1:
            return cnt

        for i in range(1, jump[idx] + 1):
            if idx + i < n and not visited[idx + i]:
                visited[idx + i] = True
                queue.append((idx + i, cnt + 1))

    return -1


print(minjump(0, 0))

2. DP 풀이

  1. i 에서 1 ~ jump[i]범위인 j만큼 점프한다.
    • i -> (i + j)로 점프
  2. dp[i+j]의 기록이 없으면, 점프 이전 위치인 i의 점프 기록인 dp[i]에서 1번 점프한 값을 넣는다.
    • dp[i+j] = dp[i] + 1
  3. 점프한 기록이 있으면, 넘어간다.
  4. 시작한 부분은 점프를 한 기록이 없으므로 dp[0] = 0이다.
    5.시작 부분을 제외한 곳에 0이 있으면 끝까지 도달하지 못했으므로 -1을 출력한다.
import sys
input = sys.stdin.readline()

n = int(input())
jump = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    for j in range(1, jump[i] + 1):
        if i + j < n and dp[i+j] == 0: 
            dp[i+j] = dp[i] + 1

if dp[1:].count(0):
    print(-1)
else:
    print(dp[n-1])

0개의 댓글