[백준] 1326 - 폴짝폴짝

문제

백준 1326번 폴짝폴짝

문제 링크 : https://www.acmicpc.net/problem/1326

 

문제 풀이

목적 : 징검다리에 적힌 숫자의 배수만큼 움직일 수 있을 때, 개구리가 a번째에서 b 번째 징검다리까지 갈 수 있는 최소 점프 수를 구하는 것

이 문제에서 개구리는 왼쪽과 오른쪽 모든 방향으로 이동할 수 있고, 징검다리 숫자의 배수만큼 점프할 수 있다. a에서 b로 가기까지 다양한 경로가 존재하고, 그 중 가장 빠른 점프 수를 찾는 것이기 때문에 '출발점에서 목적지까지의 최소거리' 를 찾는 것과 같기 때문에 BFS 알고리즘을 사용하여 해결하였다.

이 문제에서는 현 징검다리 위치와 jump 수를 큐에 넣어, 징검다리 수의 배수 중 왼쪽과 오른쪽 모든 방향에서의 방문하지 않은 징검다리를 탐색한다. visited 배열을 각 경로대로 큐에 넣지 않고 전역으로 정의한 이유는, 한 경로에서 그 징검다리 위치를 방문했다면 다른 경로에서 그 위치를 방문하더라도 처음 경로만큼 빠른 속도로 도달하지 못하기 때문에 visited 배열을 하나의 전역으로 정의하였다.

 

코드

import sys
from collections import deque

input = sys.stdin.readline

n=int(input())
lst = list(map(int,input().rstrip().split(' ')))
a,b = map(int, input().split(' '))
visited=[False]*n

q=deque([(a-1,0)])
visited[a-1]=True

answer=-1

while q:
  current,jump=q.popleft()
  if current==b-1:
    answer=jump
    break

  value=lst[current]
  tol=1
  # 왼쪽으로 가기 
  while current-value*tol>=0:
    if not visited[current-value*tol]:
      q.append((current-value*tol,jump+1))
      visited[current-value*tol]=True
    tol+=1
  # 오른쪽 탐색
  tor=1
  while current+value*tor<n:
    if not visited[current+value*tor]:
      q.append((current+value*tor, jump+1))
      visited[current+value*tor]=True
    tor+=1

print(answer)