[Algorithm] 백준_13913번: 숨바꼭질4
업데이트:
오늘의 예비문제2는 🚀 백준 13913 숨바꼭질4 이다.
숨바꼭질과 거의 유사하지만, 자신이 거쳐온 과정도 같이 프린트 해줘야 한다!
테스트케이스 이해하기
수빈이랑 동생이랑 숨바꼭질을 해서, 수빈이가 찾으러 가는 것이다.
이동할 수 있는 방법은 +1, -1, *2 방법이 있고 이동할때 마다 1초씩 흐른다.
가장 빠른 시간과 함께 거쳐온 위치를 프린트 해주면 된다!
알고리즘
기본 알고리즘은 숨바꼭질이랑 비슷하다.
-
방문했는지 확인하는 check, 각각 거리가 얼마인지 저장하는 dist, 어디서왔는지 저장하는 place를 선언한다.
-
deque를 이용해서 수빈이의 위치를 넣고, while문을 시작한다.
-
세가지 경우로 나눠서 범위를 확인하고, +1, -1, *2 씩 이동했을 경우를 생각해서 check랑 dist를 채운다
-
place[nxt]를 넣어줌으로서 어디에서 왔는지를 저장해준다.
-
현재 위치가 수빈이 동생 위치이면 프린트 하고 break 해서 탈출!
-
place를 거꾸로 타면서 result에 넣어주고 for문을 반대로 돌려서 프린트 해준다.
정답코드
from collections import deque
max=200000
a,b = map(int,input().split())
check=[False]*max
dist=[0]*max
place=[0]*max
result=[]
q = deque()
q.append(a)
check[a] = True
while q:
now = q.popleft()
if now == b:
print(dist[b])
break
for nxt in [now+1, now-1, now*2]:
if -1<nxt<max and not check[nxt]:
q.append(nxt)
check[nxt] = True
dist[nxt] = dist[now]+1
place[nxt] = now #nxt칸에 지금 위치 넣어주기. 여기를 거쳐서 왔다!
#place를 거꾸로 거슬러 올가면서 result에 append하기
result.append(b)
next = b
while next !=a:
result.append(place[next])
next = place[next]
#for문 반대로 돌리기
for i in range(len(result)-1,-1,-1):
print(result[i], end=' ')
인상깊은 재귀함수
이런 방식으로 재귀함수를 사용해서 place를 프린트 할 수도 있다. 우왕!✨
def printtool(n, m):
if n != m:
printtool(n, place[m])
print(m, end=" ")
printtool(n,m)
🚀Reference: 백준 13913 숨바꼭질4