[백준] 11060번 - 점프 점프 (Python)

 

 

11060번: 점프 점프

 

문제

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

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

입력

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

출력

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

예제

위 문제는 다이나믹 프로그래밍과 BFS로 풀 수 있다.

다이나믹 프로그래밍 풀이

1. dp 리스트를 생성한 후 처음 시작점을 0으로 초기화한다.

2. dp[i] + 1과 dp[i + j]를 비교해서 더 작은 값으로 dp[i + j]에 저장한다.

import sys

n = int(input())
graph = list(map(int, sys.stdin.readline().split()))
dp = [n + 1] * n
dp[0] = 0

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

if dp[n - 1] == n + 1:
	print(-1)
else:
	print(dp[n - 1])

BFS 풀이

1. 방문했을 때 점프 횟수를 저장하는 리스트를 생성한다.

2. 현재 위치에서 점프했을 때의 위치가 그래프 내에 존재하거나 방문하지 않았다면 현재 점프 횟수 + 1로 저장한다.

import sys; input = sys.stdin.readline
from collections import deque

n = int(input())
graph = list(map(int, sys.stdin.readline().split()))
distance = [0] * (n)

## n이 1이면 1을 출력한다.
if n == 1:
	print(0)
	exit()

def bfs(start):
	q = deque()
	q.append((start, graph[start]))
	while q:
		now, jump = q.popleft()
		for i in range(1, jump + 1):
			## 점프했을 때 그래프를 넘어가거나 이미 방문했을 때
			if now + i >= n or distance[now + i]:
				continue
			## 점프 가능하다면 현재까지 (점프 횟수 + 1)로 저장 후 큐 삽입
			distance[now + i] = distance[now] + 1
			q.append((now + i, graph[now + i]))

bfs(0)

print(distance[-1] if distance[-1] else -1)