[Python] 1326번 폴짝폴짝

✏️ 문제

 

문제 파악

현재 위치 v 에서 앞으로 graph[v] 만큼 떨어진 위치로 점프 가능한 모든 위치를 계산한다.
v + graph[v] 에서 시작해서 n 까지 graph[v] 씩 증가하면 가능한 점프 위치를 next_v 에 대입하도록 코드를 짜면 다음과 같다.

for next_v in range(v + graph[v], n, graph[v]):

 

그리고 현재 위치 v 에서 뒤쪽으로 graph[v] 만큼 떨어진 위치로 점프 가능한 모든 위치를 계산한다.

v - graph[v] 에서 시작해 0 까지 graph[v] 씩 감소하며 가능한 점프 위치를 next_v 에 대입하도록 코드를 짜면 다음과 같다.

for next_v in range(v - graph[v], 0, -graph[v]):

 

 

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

코드

from collections import deque

n = int(input())
graph = list(map(int, input().split()))
start, end = map(int, input().split())

# 징검다리 번호를 0부터 시작하는 인덱스에 맞추기 위해
start -= 1
end -= 1

def bfs(start, end, n, graph):
  visited = [-1] * n
  q = deque([start])
  visited[start] = 0

  while q:
    v = q.popleft()

    for next_v in range(v + graph[v], n, graph[v]):
      if visited[next_v] == -1:
        visited[next_v] = visited[v] + 1
        q.append(next_v)
        if next_v == end:
          return visited[next_v]

    for next_v in range(v - graph[v], -1, -graph[v]):
      if visited[next_v] == -1:
        visited[next_v] = visited[v] + 1
        q.append(next_v)
        if next_v == end:
          return visited[next_v]

  return -1

result = bfs(start, end, n, graph)
print(result)

 

 

 

---

 

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

[알고리즘] DFS와 BFS