[Python] 11060번 점프 점프

✏️ 문제  

 

문제 파악

처음에는 위의 사진과 같이 해당 범위 내에 있는 값 중 제일 큰 값과 그 값의 인덱스 값을 받아와 제일 큰 값이 있는 인덱스로 점프하는 방향으로 코드를 짰다. 점프한 인덱스의 visited 배열에 1을 넣어 최종적으로 sum(visited)을 출력하는 코드를 짰는데 자꾸 값이 몇 개는 맞으면 몇 개는 1씩 차이가 났었다. 

 

• 반례 모음 

7
2 3 1 2 6 4 7
# 3

10
1 2 0 1 3 2 1 5 4 2
# 5

2
0 0
# -1

3
2 5 0
# 1

102
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
# 101

10
1 7 1 1 1 1 3 1 0 1
# 3

5
2 1 1 0 2
# -1

3
0 1 0 
# -1

1
0
# 0

 

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 다이나믹 프로그래밍

 

 

코드

• 틀린 코드 

from collections import deque

n = int(input())
graph = list(map(int, input().split()))
visited = [0] * n

def bfs(x):
  q = deque([x])

  while q:
    max_value = 0
    max_index = 0
    index = q.popleft()

    if index + graph[index] >= n-1:
      return sum(visited) + 1

    for i in range(index + 1, index + graph[index] + 1):
      if max_value <= graph[i]:
        max_value = max(max_value, graph[i])
        max_index = max(max_index, i)

    index = max_index

    if visited[index] == 0:
      q.append(index)
      visited[index] = 1
  
  return -1

print(bfs(0))

• 맞는 코드

from collections import deque

n = int(input())
graph = list(map(int, input().split()))
visited = [-1] * n

def bfs(x):
  q = deque([x])
  visited[x] = 0
  
  while q:
    index = q.popleft()
    
    for i in range(1, graph[index] + 1):
      next_index = index + i
      
      if next_index >= n: 
        continue
      
      if visited[next_index] == -1: 
        visited[next_index] = visited[index] + 1 
        q.append(next_index)
  
  return visited[n-1]

result = bfs(0)
print(result if result != -1 else -1)

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS