[BOJ] 1326 폴짝폴짝 (Python3)

문제

개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.

입력

첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리에서 시작하여 b번 징검다리에 가고 싶다는 뜻이다. 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 개구리가 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프하여 갈 수 있는 지를 출력하시오. a에서 b로 갈 수 없는 경우에는 -1을 출력한다.

예제 입력 1  복사
5
1 2 2 1 2
1 5 
예제 출력 1  복사
1 ## 힌트 1번 징검다리에 1이 쓰여 있으므로, 1의 배수인 4만큼을 한 번에 뛰어 5번 징검다리로 갈 수 있다. ## 풀이 bfs를 이용하여 징검다리에 인덱스 + 징검다리에 적혀있는 크기의 배수들에 모두 방문하여 방문하지 않은 징검다리라면 visited에 1을 더해주는 방식으로 몇번만에 b에 도달했는지가 visited에 1보다 큰 수로 저장되도록 한다.

간단한 bfs문제이지만 푸는데 한참걸렸는데, 징검다리가 왼쪽으로도 이동할 수 있다는 사실을 생각을 안하고 계속 풀어서 아무리 반례를 찾으려 해도 찾을 수 가 없어 시간을 너무 많이 잡아먹었다. 문제를 잘읽고 프로그램을 어떤 상황까지 구현해야 하는지 확실하게 풀어야겠다.

코드

from collections import deque

def bfs(x):
    q = deque()
    q.append(x)
    visited[x] = 1
    while q:
        nx = q.popleft()
        dx=[]
        for i in range(b+1):
            if abs(bridge[nx]*-i) > n:
                break
            dx.append(bridge[nx]*i)
        for i in range(b+1):
            if abs(bridge[nx]*-i) > n:
                break
            dx.append(bridge[nx]*-i)
        for i in range(len(dx)):
            sx = nx + dx[i]
            if 0 <= sx < n and visited[sx]==0:
                visited[sx] = visited[nx]+1
                q.append(sx)
                #print('result:', result)

n = int(input())
bridge = list(map(int,input().split()))
a,b = map(int,input().split())
visited = [0]*n
result = [0]*n
bfs(a-1)
if bridge[a-1] == 1:
        print(1)
elif a == b:
    print(0)
else:
    print(visited[b-1]-1)

5
2 3 1 2 3
5 2
[0, 3, 0, -3]
[0, 3, 0, -3]
1