[파이썬 알고리즘 문제풀이] - Section7 / 깊이/넓이 우선 탐색(DFS, BFS) 활용 - 7

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

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

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

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

▣ 입력예제 1
5 14

▣ 출력예제 1
3

import sys
# sys.stdin = open("input.text", "rt")
from collections import deque

s,e = map(int, input().split())
#최대 좌표수만큼 만들어주면 돼.
MAX = 10001
dis = [0] * MAX
ch = [0] * MAX

ch[s] = 1 #현재 위치는 방문 표시 후 시작.
#출발점은 s인데 어차피 시작거리는 0
dq = deque()
dq.append(s) #현재 위치 추가해주고 시작하는거야!

dx = [-1,1,5] #방향 총 3가지 +1, -1, +5
while dq:
    now = dq.popleft() #현재위치 꺼내서
    if now == e: #목표지점에 도착하면 끝이지.
        break
    for i in range(3):
        nx = now + dx[i]
        if 0<=nx<MAX: # 좌표 범위 내에 있으면서
            if ch[nx] == 0: #방문 전이라면.
                dq.append(nx)
                ch[nx] = 1 
                dis[nx] = dis[now] + 1 #위치 갱신까지.

print(dis[e]) #목표지점에 도착하면

코멘트

이 문제는 BFS로 최단거리를 푸는 문제였다. BFS 역시 상태트리로 현재 노드(현재 위치)에서 몇가지가 뻗어나가는지 먼저 생각하고, 최단거리를 구하는 유형이라면 바로 BFS로 풀어야겠구 생각할 수 있을정도면 충분하다.

또한 시작지점 방문처리 후 반복문 시작, 현재 위치 + 1 갱신, 중복 체크

• 이 정도만 사전에 생각하고 들어가면 좋을 것 같다.