[백준, 파이썬, 5014번] 스타트링크

풀이

• dfs, bfs 문제집에 있는 문제로
• 해당 알고리즘을 활용해야 한다는 것을 알고 있었기에 간단히 해결할 수 있었는데
• 만약 모르는 상황이었다면 좀 걸렸을 것 같다.
• 우선 현재인 s 층에서 u,d 버튼을 눌렀을 때 지정 범위 내에 있다면
• 모두 이동할 수 있게 하는데 여기서 
• 무한 순회하지 않도록 방문 표시를 하여 해결할 수 있도록 했으며
• bfs는 탐색하기 전에 모든 경우에 대해 추가 후 탐색을 하는 것이기에
• q에 추가하기 전에 먼저 방문 표시를 하여 해결하도록 했으며
• bfs는 모든 경우를 하나씩 확인하는 것이기에
• 가장 먼저 결과에 다다른 것이 가장 빠른 방법이기 때문에
• while문을 바로 탈출하도록 하여 해결.

 

import sys

from collections import deque

# dfs 활용

f,s,g,u,d = map(int,input().split())

result = sys.maxsize

visit = [False]*(f+1)

visit[s] = True # dfs는 방문하기 전 방문 체크해야 중복 X

q = deque([[s,0]])

while q:

    now,cnt = q.popleft()

    if now == g:

        result = min(result, cnt)

        break

    else:

        for nt in [now+u,now-d]:

            if 0<nt<=f and not visit[nt]:

                visit[nt] = True

                q.append([nt,cnt+1])

if result == sys.maxsize: print("use the stairs")

else: print(result)