[Python/파이썬] 백준 11060번 점프 점프

11060번: 점프 점프

 

문제

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

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

입력

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

출력

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

코드

DP를 이용한 풀이

n = int(input())
arr = list(map(int, input().split()))

dp = [1001] * n
dp[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]+1, dp[i+j])
print(dp[n-1] if dp[n-1] != 1001 else -1)

dp배열에 각 칸까지 도달하는데 필요한 최소 점프의 횟수를 저장하도록 했다.

가장 왼쪽칸부터 오른쪽으로 한 칸씩 이동하며 해당 칸에(i)서 점프해서 갈 수 있는 칸(i+j)들의 원래 dp값보다 i번째에서 1번 더 점프해서 가는 값(dp[i]+1)이 더 작다면 그 값으로 갱신해주도록 했다.

 

 

BFS를 이용한 풀이

from collections import deque

n = int(input())
arr = list(map(int, input().split()))

visited = [False] * n
q = deque([(0, 0)])
visited[0] = True
while q:
    now, cnt = q.popleft()
    if now == n-1:
        print(cnt)
        exit()
    for i in range(1, arr[now]+1):
        if now+i < n and not visited[now+i]:
            q.append((now+i, cnt+1))
            visited[now+i] = True
print(-1)

• 가장 왼쪽 칸인 0번째 칸에서 출발한다.
• 점프해서 갈 수 있는 칸들 중 아직 방문하지 않은 칸이 있다면 q에 넣고 방문 처리를 한다.
• now가 가장 오른쪽 칸인 n-1에 도달한다면 그 때까지 점프한 횟수인 cnt를 출력하고 프로그램을 종료한다.
• 만약 q가 비워질 때까지 프로그램이 종료되지 못했다면 가장 오른쪽 칸에 가는 방법이 없다는 뜻이므로 -1을 출력한다.