송아지 찾기(BFS : 상태트리탐색)
5637 단어 파이썬 알고리즘 문제풀이파이썬 알고리즘 문제풀이
깊이/넓이 우선 탐색(DFS, BFS) 활용
문제 ✏️
송아지 찾기(BFS : 상태트리탐색)
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.
▣ 출력설명
점프의 최소횟수를 구한다.
▣ 입력예제 1
5 14
▣ 출력예제 1
3
코드 💻
'''
BFS는 한번에 갈 수 있는 노드를 모두 큐에 넣는다. 들어간 순서대로 탐색
'''
import sys
from collections import deque # queue
#sys.stdin = open("input.txt", "rt") # read text
MAX = 100000 # 좌표의 maximum
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])
참고
- 인프런 : 파이썬 알고리즘 문제 풀이
Author And Source
이 문제에 관하여(송아지 찾기(BFS : 상태트리탐색)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsj3282/송아지-찾기BFS-상태트리탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)