[TIL] 백준 1326 - 폴짝폴짝 ( python )

📌 문제 탐색하기

N : 징검다리의 개수

arr : 각 징검다리에 쓰여 있는 N개의 정수

a, b : a, b번 징검다리 ( N보다 작거나 같은 정수 )

개구리가 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있으며, a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 구하는 것이 핵심입니다.

N은 최대 10,000입니다.

가능한 시간복잡도

최악의 경우, 모든 돌에 1이 적혀 있다고 가정하면, 각 돌에서 최대 O(N)개의 후보를 확인해야 합니다.

1. O(N) * O(N) 이라면?
   1. 10,000² = 100,000,000번의 연산이 발생

1초에 약 100,000,000번의 연산을 수행할 수 있으므로 시간안에 탐색을 완료할 수 있습니다.

알고리즘 선택

시작 노드를 기준으로 거리가 가까운 노드를 먼저 방문하는 방식인 BFS 알고리즘으로 접근해보겠습니다.

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. 방문 체크를 위한 visited 배열을 초기화합니다.(-1)
3. BFS 탐색을 구현합니다.
   1. 초기 시작 노드를 방문 체크한 후 queue에 넣습니다.
   2. queue의 맨 앞 노드를 탐색합니다.
   3. 오른쪽으로 이동할 수 있는 노드를 탐색하며, 방문하지 않았을 경우 최단거리 +1을 하고 queue에 넣습니다.
   4. 왼쪽으로 이동할 수 있는 노드를 탐색하며, 방문하지 않았을 경우 최단거리 +1을 하고 queue에 넣습니다.
4. 최종 목적지에 도달하면 값을 리턴하고 출력합니다.

---

📌 정답 코드

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

def bfs():
    q = deque()
    visited = [-1 for _ in range(N)]

    q.append(a - 1)
    visited[a - 1] = 0

    while q:
        now = q.popleft()

        for i in range(now, N, arr[now]):
            if visited[i] == -1:
                q.append(i)
                visited[i] = visited[now] + 1
                if i == b - 1:
                    return visited[i]
        for i in range(now, -1, -arr[now]):
            if visited[i] == -1:
                q.append(i)
                visited[i] = visited[now] + 1
                if i == b - 1:
                    return visited[i]
    return -1


N = int(input())
arr = list(map(int, input().split()))
a, b = map(int, input().split())

print(bfs())