[백준] 1326: 폴짝폴짝 (파이썬)

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

난이도: 실버2

▶ 문제 탐색하기

재귀함수를 이용해서 최소한 점프할 수 있는 방법을 탐색한다. 

 

◇ 입력

1. 징검다리 개수 N (1~10,000 정수)
2. N개의 징검다리에 쓰여진 자연수 ---> arr =[]
3. 시작 a번째 징검다리, 도착 b번째 징검다리

 ◇ 원하는 출력 조건

1.  a번 징검다리에서 b번 징검다리로 최소 몇 번 점프해서 갈 수 있는지? 
2. 만약 갈 수 없다면 -1 출력  

가능한 시간복잡도 

 

알고리즘 선택

- BFS 알고리즘 사

▶ 코드 설계하기

 1. 가장 먼저, arr[ a-1 ] 시작점 값과 뛰어야하는 전체 거리 ( b-a )를 찾는다. 

 

 2. 만약 전체 거리가 시작점 값으로 나누어 떨어진다면 한 번에 뛰어 건널 수 있다.

①  if (b-a) % arr[a-1] == 0,  return 1

②  else: 나머지가 생긴가면? 극한의 상황을 생각해야하는데

 

 3. a에서 b로 갈 수 없는 경우? return -1

① 시작점 값 arr[ a-1 ] 이 전체 거리 ( b-a ) 보다 클 때

② if (b-a) % arr[a-1] == 0,  return 1

 

▶ 회차별 수정사항

• 개구리는 앞으로만 움직인다고 생각했는데 그런 조건은 적혀있지 않았다. 앞뒤로 움직일 수 있는 개구리였다
•  

▶ 정답 코드

from collections import deque

n = int(input())
bridge = [0] + list(map(int, input().split()))
start, end = map(int, input().split())


def bfs(s, e):
    q = deque([s])
    visited = [-1] * (n + 1)
    visited[s] = 0
    while q:
        now = q.popleft()
        for i in range(now, n + 1, bridge[now]): # 오른쪽 방향
            if visited[i] == -1:
                q.append(i)
                visited[i] = visited[now] + 1
                if i == e:
                    return visited[i]
        for i in range(now, 0, -bridge[now]): # 왼쪽 방향
            if visited[i] == -1:
                q.append(i)
                visited[i] = visited[now] + 1
                if i == e:
                    return visited[i]
    return -1 # 찾지 못한 경우


print(bfs(start, end))

 

▶ 추가 풀이