64)송아지 찾기(BFS: 상태트리탐색)

문제

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하기

 

조건

현수의 위치와 송아 지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

 

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.

 

제한사항

첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다.

 

직선의 좌표 점은 1부터 10,000 까지이다.

 

점프의 최소횟수를 구한다.

 

문제풀이

from collections import deque

MAX=10000
ch=[0]*(MAX+1)
dis=[0]*(MAX+1)
S, E=map(int, input().split())
ch[S]=1
dis[S]=0
dQ=deque()
dQ.append(S)

while dQ:
  now=dQ.popleft()
  
  if now==E:
    break

  for next in (now-1, now+1, now+5):
    if 0<next<=MAX:
      if ch[next]==0:
        dQ.append(next)
        ch[next]=1
        dis[next]=dis[now]+1

print(dis[E])