[Python Algorithm] 깊이/넓이 우선탐색(DFS, BFS) - 송아지 찾기(BFS)

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (BFS 편)

BFS는 레벨 탐색 ! => 큐 사용

 

 

📖 문제 : 송아지 찾기

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요.

 

 

입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다.

 

출력설명
점프의 최소횟수를 구한다.

 

입력예제 1

5 14

 

출력예제 1

3

 

import sys
input = sys.stdin.readline
from collections import deque

MAX = 10000
ch = [0] * MAX
dis = [0] * MAX

n, m = map(int, input().split())
ch[n] = 1
dis[n] = 0
dQ = deque()
dQ.append(n)

while dQ:
  now = dQ.popleft()
  if now==m:
    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[m])

 

 

⭐️ Point ! ⭐️

• for next in(now-1, now+1, now+5):
  next의 값이 now-1, now+1, now+5의 세가지의 값으로 3번 for문이 도는 것 !
  그래프의 가지가 세가지의 방향으로 뻗어나가기 위한 방법 !
  
  
• dis에는 몇 번만에 갔는지 ! 자신의 부모 +1 값이 들어감
  
  
• BFS이기 때문에 14라는 수가 나오는 그 즉시 dis[14]의 값을 출력하면 된다. 14가 나온 Level 값 !이 가장 빠른 값이다. 
  
  
•  

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이