[인프런] 송아지 찾기

---

문제설명

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

입력조건

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

출력조건

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

사고과정

• 그동안 매번 DFS를 풀다가 이 문제를 풀 때도 자연스레 DFS로 풀려고 했다. 하지만 BFS로 풀어야 햇던 문제이다.. 아직 BFS에 대해서는 많이 풀어보지 못해서 아이디어가 잘 안떠오르는 걸 직감하고 풀이 강의에서 아이디어만 보고 구현에 도전했다.
• BFS도 마찬가지로 상태트리를 만들긴 해야 하는데 DFS때랑은 좀 달랐다. 상태트리의 한 레벨씩 모두 탐색하는 점이 다르다. 또 DFS는 스택을 사용하지만 BFS는 큐를 활용한다는 점도 다르다.
• 그리고 BFS에서는 주로 그래프 데이터에서 간선 비용이 동일할 때, 최솟값을 찾는 문제유형이라고 책에서 배웠었던 적이 있다.
• 해당 문제에서는 거리 테이블을 정의해서 이것으로 해당 노드를 방문했는지 여부와 이동 횟수를 동시에 기록했다.
• 문제에서는 거리 테이블, 방문 테이블을 따로 정의했다. 이렇게 해도 좋을 듯 하다!

풀이(스스로 못 푼 풀이)

- 나의 풀이

s, e = map(int, input().split())
move = [1, -1, 5]
MAX = int(1e4)
distance = [-1] * (MAX+1)
distance[s] = 0  # 출발지점 거리 0으로 초기화
queue = deque([s])

while queue:
    pos = queue.popleft()
    if pos == e:
        break
    # 3가지 방법으로 이동
    for m in move:
        if 0 < pos + m <= MAX: # 이 조건이 없으면 마지막 인풋 오답나옴
            if distance[pos + m] == -1:  # 방문한 곳 아니라면!
                distance[pos + m] = distance[pos] + 1
                queue.append(pos + m)

print(distance[e])

- 강좌 풀이

n, m = map(int, input().split())
MAX = int(1e4)
ch = [0] * (MAX+1)
dis = [0] * (MAX+1)
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])