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

난이도 : Silver2
Link : https://www.acmicpc.net/problem/11060
Tag : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색
풀이일자 : 2024년 9월 28일

📌 문제 탐색하기

N : 미로의 크기
grid : 미로칸마다 점프 할 수 있는 값

이 문제는 각 칸의 숫자만큼 점프를 할 수 있으며 마지막 칸에 도달할 수 있는지 확인하는 문제이다. 마지막 칸으로 도달할때는 최소 점프 갯수를 구해야 한다.

가능한 시간복잡도

N(1 ≤ N ≤ 1,000)
grid(0 ≤ grid ≤ 100)
이므로 각 모든 칸의 점프 할 수 있는 경우의 수를 전부 구하는 것은 시간 복잡도 상 문제가 있을것으로 보여 BFS를 통해 처음으로 마지막 칸에 위치하는 곳이 가장 적은 점프를 통해 도달한 것이므로 BFS를 통해 문제를 접근 하고자 한다.

📌 문제 접근 방법

BFS는 최소 경로를 찾는 데 적합한 알고리즘이기 때문에, 처음으로 도달할 수 있는 끝 칸에 도착하면 그것이 최소 점프 횟수가 된다.

따라서 이 문제는 BFS를 통해 문제를 접근한다.

📌 코드 설계하기

1. N과 grid를 입력받는다.

2. queue에 현재 위치, 점프 횟수를 추가한다.

3. vistied 배열에 방문한 위치를 추가한다.

4. answer를 -1로 초기화 한다.

5. BFS 알고리즘을 진행한다.

   • 현재위치와 점프 횟수를 queue에서 꺼낸다.
   • 만약 현재 위치가 마지막 칸이라면 반복문을 종료하고 answer = step으로 업데이트한다.
   • 그렇지 않을때 해당칸에서 갈 수 있는 곳들을 체크한다.

   
   for i in range(1, grid[now]+1):
       can_jump =  now + i
       if can_jump < N and can_jump not in visited:
           queue.append((can_jump, step + 1))
           visited.append(can_jump)

6. answer를 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

from collections import deque

N = int(input())
grid = list(map(int, input().split()))

queue = deque([(0, 0)]) #위치, 점프횟수
visited = [0]
answer = -1

while queue:
    now, step = queue.popleft()
    if now == N - 1:
        answer = step
        break

    #현재칸에서 갈 수 있는 곳 체크
    for i in range(1, grid[now]+1):
        can_jump =  now + i
        if can_jump < N and can_jump not in visited:
            queue.append((can_jump, step + 1))
            visited.append(can_jump)

print(answer)