문제
처음 이 문제를 보자마자 미로찾기 문제와 비슷하지만 상하좌우로 이동하는 것이 아닌 위로 u, 아래로 d 만큼 이동하는 문제구나 라는 생각이 들었다.
그러므로 bfs 알고리즘을 이용하여 이 문제를 해결해주었다.
코드
from collections import deque
f, s, g, u, d = map(int, input().split())
def bfs(f,s,g,u,d):
q = deque()
visited = [0 for _ in range(f+1)]
visited[s] = 1
q.append(s)
while(q):
s = q.popleft()
#원하는 목적지에 도달하면 break
if s == g:
break
else:
for ns in (s + u, s - d):
if 0< ns <=f and visited[ns] == 0:
q.append(ns)
visited[ns] = visited[s] + 1
#목적지에 도달하지 않은 채 while 문이 끝났었다면
if s != g:
print("use the stairs")
else:
#목적지에 도착했을때 +1이 된 상태이므로 -1을해주어 출력
print(visited[g]-1)
bfs(f,s,g,u,d)처음에는 visited 리스트를 방문만 하면 1로 바꾸어 방문처리만 해주려고 했는데 그런 방식으로 했을 때에는 원하는 답을 찾을 수가 없었다.
그리고 처음에 층의 범위를 0이상으로 생각했는데 0층은 존재하지 않으므로 이점 또한 유의해야한다.
