백준 11060 점프 점프 문제풀이 (Python)

백준 11060 점프 점프 문제입니다.

배열의 첫번째 위치에서 마지막 위치로 이동하는 문제입니다.

이동은 현재 위치의 값만큼 이동할 수 있습니다.

저는 DP와 dfs를 통해 문제를 해결하였습니다.

1. 이동하려는 위치에 방문한 적이 없다면

- 무조건 방문을 수행합니다.

2. 이동한 위치를 방문했다면

- 해당 dp 값보다 현재 값이 작아 갱신할 수 있다면 방문을 수행합니다.

최종 출력은 배열의 마지막 요소에 방문하기 위한 경로가 존재한다면 그 값을, 없다면 -1을 출력합니다.

N = int(input())
dp = [0] * N
arr = list(map(int, input().split()))
find = [False]


def dfs(temp, depth):
    if temp == (N - 1):
        find[0] = True
        return
    mv = arr[temp]
    for i in range(1, mv + 1):
        if (i + temp) >= N:
            break
        if dp[temp + i] == 0:
            dp[temp + i] = depth + 1
            dfs(temp + i, depth + 1)
        else:
            if dp[temp + i] > (depth + 1):
                dp[temp + i] = depth + 1
                dfs(temp + i, depth + 1)


dfs(0, 0)
if find[0]:
    print(dp[N - 1])
else:
    print(-1)

 

출처

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

11060번: 점프 점프