[백준] 1326번, 폴짝폴짝

# BFS

 

https://www.acmicpc.net/problem/1326

1326번: 폴짝폴짝

 

문제

개구리가 징검다리를 건너는데, 다리에는 각각 숫자가 써져있음

그 숫자의 배수만큼은 그냥 갈 수 있다.

출발지와 목적지가 주어졌을 때, 목적지까지 가는데 얼마나 걸리는지 구하기

 

▶ 내가 지금 밟은 칸이 1이 되면 다 갈 수 있음  → 시간 무조건 1

▶ 배수 만큼은 갈 수 있다고 했으니까 뒤로도 가능함

 

BFS방식으로 풀었다

 

 

풀이

from collections import deque

def polzzak(start, end):    # start와 end는 인덱스, 예제에서는 0, 4
    d = end - start     # 출발지와 목적지 사이의 거리
    startvalue = stone[start]
    visited = [0 for _ in range(10001)]
    visited[start] = 1

    # 만약 시작점에서 바로 갈 수 있다면 바로 리턴
    if d % startvalue == 0:
        return 1
    
    que = deque([(start, 1)])   # 현재의 인덱스, 레벨
    while que:
        nowidx, level = que.popleft()
        # print(stone[nowidx], level)
        nowvalue = stone[nowidx]
        # 현재 위치와 도착지 사이의 거리
        now_d = end - nowidx
        if now_d % nowvalue == 0:
            return level
        
        # 다음으로 갈 수 있는 곳
        nextdol = []
        # 오른쪽으로 갈 수 있는 곳
        k = nowidx
        while k <= 10000 - nowvalue:
            k += nowvalue
            nextdol.append(k)
		
        # 왼쪽으로 갈 수 있는 곳
        l = nowidx
        while 0 <= l:
            l -= nowvalue
            nextdol.append(l)


        for nextidx in nextdol:
            if 0 <= nextidx < len(stone) and visited[nextidx] == 0:
                visited[nextidx] = 1
                que.append((nextidx, level + 1))
    return -1



N = int(input())
stone = list(map(int,input().split()))
a, b = map(int,input().split())
print(polzzak(a - 1, b - 1))

---

반례고 뭐고 예시가 하나밖에 없어서 힘들었다....

그래서 대충 아무 숫자만 넣으면서 디버깅했다

BFS활용방법이 무궁무진하다,..