[알고리즘] 송아지 찾기(BFS : 상태트리탐색)

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

---

현수는 송아지를 잃어버렸다.

다행히 송아지에는 위치추적기가 달려 있다.

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

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

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

입력설명

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

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

출력설명

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

테스트케이스

입력예제	출력예제
5 14	3
8 3	5
13 35	6
1 21	4
3 4356	873
7 8945	1790

---

동작 시각화

---

코드

from collections import deque

# 좌표의 MAX
MAX = 10000

# 각 좌표를 리스트로 생성
# 들어갈 수 있는 것의 값 -> 0 ~ MAX 까지
ch = [0] * (MAX + 1)
dis = [0] * (MAX + 1)

s, e = map(int, input().split())

# 처음 n에서 시작을 하니깐 n을 체크한다 (Level 1)
ch[s] = 1
# 거리는 0 출발 점이기 때문에
dis[s] = 0

# 큐를 생성
dQ = deque()
# 첫 root 노드 삽입
dQ.append(s)

while dQ:
    # 큐에서 하나를 꺼낸다
    now = dQ.popleft()
    # 넣은 큐 값에서 빼는 값이 m과 같을 경우 끝낸다!
    if now == e:
        break
    # 차례 차례 3 바퀴를 돈다 (튜플)
    # 자식으로 가지치기
    for next in (now-1, now+1, now+5):
        # next라는 값이 범위에 있고
        if 0 < next <= MAX:
            # 방문하지 않은 장소일 경우
            if not ch[next]:
                # 큐에 next라는 값을 대입
                dQ.append(next)
                # 방문을 했다는 것을 체크
                ch[next] = 1
                # 레벨을 가르키는 것이다!
                # 몇번을 돌았는지 (pop한 내용의 위치에 있는 dis + 1을 하여 Level을 올린다)
                dis[next] = dis[now] + 1

    # dis[m]에 저장되어있는 값을 통해서
    # 몇번 안에 갔는지 알 수 있다.
print(dis[e])