[완전탐색][상태트리탐색] - 송아지 찾기(BFS)

문제

s는 현재 나의 위치 e는 송아지의 위치로 +1, -1, +5 만큼만 이동할 수 있다고 할 때 우리는 최소 몇번의 움직임으로 송아지를 찾을 수 있을지 출력하세요

문제 풀이 -next 함수 사용

from collections import deque


s, e = map(int,input().split())
MAX = 10000
ch = [0] * (MAX+1)
dis = [0] * (MAX +1)
a = [-1,1,5]
ch[s] = 1 #시작 노드는 체크를 해준 표시를 해야 된다!
dis[s] = 0 #시작 노드의 거리값은 0이다.
q = deque()
q.append(s)

while q:
    now = q.popleft()
    if now == e:
        break
    for next in(now-1, now+1, now+5):
        if 0 < next <= MAX and ch[next]==0:
            q.append(next)
            ch[next] = 1
            dis[next] = dis[now] +1
        

print(dis[e])

• next 함수를 사용해서 해당 범위를 다음 변수로 줄 수 있습니다.
• 이때 q에 들어가며 해당 부모 노드에 연결된 자식 노드를 싹 다 돈 다음 다음 자식으로 넘어가는 방식인 BFS를 사용하기 위해서는 큐를 사용합니다.
• ch라는 체크를 위한 리스트 변수 하나와 dis라는 해당 거리가 몇번에 걸쳐서 갔는지를 확인할 수 있는 dis 리스트 변수를 주어 진행합니다.
• 이때 for문을 도는데 조건은 간단합니다 최대 값이 10000을 넘지 않는다는 조건이 있어 상수로 만든 MAX 상수를 사용하고 0보다 크고 MAX 값보다 작거나 같으며 한 번도 확인하지 않았던 거리라면 노드를 다음 노드로 넘겨 진행합니다.
• 이때 현재 popleft() 한 값이 송아지가 있는 거리와 같다면 while 문을 종료합니다.
  • 이유는 간단합니다. 아래 노드로 더 뻗어나가서 확인하면 이보다 더 큰값이 답이 되기 때문입니다.(최소 횟수를 구하는 문제라 그만 끝내주어야 합니다)
• 마지막으론 현재 송아지가 있는 값에 우리가 몇번의 이동만에 도착했는지를 표시해줍니다.

문제 풀이 - 이동 구간을 담은 리스트를 사용한 경우

from collections import deque


s, e = map(int,input().split())
MAX = 10000
ch = [0] * (MAX+1)
dis = [0] * (MAX +1)
a = [-1,1,5]
ch[s] = 1 #시작 노드는 체크를 해준 표시를 해야 된다!
dis[s] = 0 #시작 노드의 거리값은 0이다.
q = deque()
q.append(s)

while q:
    now = q.popleft()
    if now == e:
        break
    for next in a:
        if 0 < now + next <= MAX and ch[now + next] == 0:
            ch[now + next] = 1
            dis[now+next] = dis[now]  + 1
            q.append(now+next)
        
    
print(dis[e])

• next 사용이 훨씬 편하지만 주어진 거리가 많아진다면 이 방법을 알아야 한다!