파이썬 알고리즘-60 (DFS/BFS 활용) 송아지 찾기

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

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

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

▣ 입력예제 1
5 14

▣ 출력예제 1
3

내 코드

def bfs(v):
    global cnt, s
    if v>cnt:
        return
    if s==e:
        
        if v<cnt:
            cnt=v
    else:
        if s>e:
            s-=(s-e)
            bfs(v+(s-e))
        if (e-s)//5>=1:
            s+=(((e-s)//5)*5)
            bfs(v+((e-s)//5))
        else:
            s+=1
            bfs(v+1)
        
s,e=map(int,input().split())
cnt=int(1e10)
bfs(0)
print(cnt)

bfs방식을 제대로 이해하지 못했다. 시작과 출발점의 차이가 5 이상이면 그것을 나눈 몫에 5를 곱해 시작값에 더했고, 나눈 몫을 v(횟수)에 더했는데 v값이 저장이 안되는 것 같았다.

풀이

from collections import deque

MAX = 10000
ch = [0] * (MAX+1)
dis = [0] * (MAX+1)
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])

반성점

• BFS는 분명 배웠는데 아무것도 기억나지 않는다.

배운 것

• BFS는 최단거리를 구할 때 사용한다. 대략적인 구현 방법은 deque의 초기값으로 출발점을 넣고 pop한 뒤, pop한 점에서 한번에 갈 수 있는 도착점들을 deque에 순서대로 넣는다. 이 때 도착점들은 방문한 적이 없는 상태일 때만 deque에 넣는다. 넣었다면 방문한 것을 체크해준다. 그리고 거리는 출발점을 0으로 두고 pop한 점의 거리에 +1을 해준다.