.PNG)
61. 송아지 찾기(BFS : 상태트리탐색)
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아
지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과
같은 방법으로 이동한다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수
있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성
하세요.
▣ 입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000
까지이다.
▣ 출력설명
점프의 최소횟수를 구한다.
▣ 입력예제 1
5 14
▣ 출력예제 1
3
<내 풀이>
처음 배워서 강의를 들으며 BFS개념을 배우고 따라쳐보았음
<풀이>
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])
<반성점>
- que의 부분을 상당부분 까먹었음
- 여기선 def DFS 같이 하는 것 아니고
from collections import deque 로 데큐를 불러내는 방식
<배운 점>
- BFS : 넓이 우선 탐색
- 레벨로 탐색하는 것, 큐를 이용해서
- 하나가 pop되면 그에 연결되어 있는 아이들 들어오고 하는 것의 반복
- 최단 거리 구할 때 多사용
now=dq.popleft()
if now==m :
break
for next in(now-1, now+1, now+5) :이와 같이 하나가 pop 되면 세개가 반복해서 나오게 되는 것을 이렇게 표현할 수도 있음
2회독 내 풀이
=> 아쉽게도 밑에 같이 아주 허접하게만 구현함..(엉망진창)
놓친 점들 : <아주 많음 주의>
- ch리스트 만드는 것 - ch 0이면 q에 넣어주고 ch를 1로 표시해주는 것(최단)
- max만드는 것 (범위) -maxi 보다 1크게
- dis 만드는 것 (거리 구하기) - maxi 보다 1 크게
다 빼먹었음..ㅋㅋㅋㅋㅋ 수업 제대로 안듣고 복습안했던 것이 제대로 들통났음- 그리고 dis[s]=0, ch[s]=1 로 표시도 해줘야 함
s,e=map(int,input().split())
q=deque()
q.append(s)
while q:
k=q.popleft()
if k==e:
break
for i in range(3):
s+=k-1
s+=k+1
s+=k+5
==> 수정 후 풀이
from collections import deque
maxi=10000
ch=[0]*(maxi+1) # 최단 거리 구할 땐 체크리스트가 필수지
dis=[0]*(maxi+1) # 또 최단거리 구할 때 거의 거리 리스트도 필요하지, 얼마만에 도달했나 보기 위해서는
s,e=map(int,input().split())
ch[s]=1 #처음에 출발하는데로는 다시 돌아오면 최소 경로가 아니므로 체크
dis[s]=0 #처음 스타트 하기 시작위한 자리는 0으로 초기화
q=deque()
q.append(s)
while q:
k=q.popleft()
if k==e:
break
for i in (k-1,k+1,k+5): #경우의 수가 세개뿐이므로 돌려주기
if 0<i<=maxi: #범위의 좌표안에 있는지 체크 필요
if ch[i]==0: #체크 안돼있는 애라면
ch[i]=1 #체크해주구
q.append(i) #큐에 넣어주구
dis[i]=dis[k]+1 #거리는 처음애보다 1더하기
print(dis[e])
