BFS(넓이 우선 탐색) 익히기 _ 송아지찾기문제

김태원 선생님의 강의를 들으면서!

아무래도 나같이 찬찬한 이해의 시간이 필요한 사람에겐 필기/그림으로 먼저 정리하고 코드로 쓰는 게 좋은 것 같다!! 

+ 어제 종이질감필름 사길 너무 잘했다..ㅎㅎ

import collections
def findCow(start:int, destination: int, max_position: int):
    positions_que = collections.deque()
    positions_que.append(start)
    distance = [0] * (max_position + 1)
    distance[start] = 0
    checked = [0] *(max_position + 1)

    while positions_que:
        now = positions_que.popleft()
        if now == destination:
            break
        for next in (now-1, now+1, now+5):
            if 0 < next <= max_position:
                if checked[next] == 0:
                    positions_que.append(next)
                    checked[next] = 1
                    distance[next] = distance[now] + 1

    return distance[destination]

# 예제 확인 print(findCow(5, 14, 10000))