🥚문제링크

https://www.acmicpc.net/problem/5014

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

🍳코드

import sys
from collections import deque
input = sys.stdin.readline

F, S, G, U, D = map(int, input().split())

visited = [False]*(F+1)


def bfs(S):
    # q에 (층, 버튼 수) 저장
    q = deque([(S, 0)])
    visited[S] = True

    while q:
        floor, btn = q.popleft()
        # G층에 도착
        if floor == G:
            return btn

        # U버튼
        if floor + U <= F:
            if not visited[floor + U]:
                q.append((floor + U, btn + 1))
                visited[floor + U] = True
        # G버튼
        if 1 <= floor - D:
            if not visited[floor - D]:
                q.append((floor - D, btn + 1))
                visited[floor - D] = True

    return "use the stairs"


print(bfs(S))

---

🧂아이디어

탐색, BFS

1. (시작 층, 버튼을 누른 횟수인 0)을 큐에 삽입한다.
   visited[시작층] = True로 방문표시를 한다.

2. 큐의 첫 원소를 pop하여 층수 floor, 버튼을 누른 횟수 btn을 얻는다.

3. 층수가 G이면 btn을 리턴한다.

4. floor+U만큼, floor-G만큼 이동한 위치가 범위 내에 있고, 아직 방문 표시가 되지 않았다면 (이동 층, btn + 1)을 큐에 삽입한 뒤 visited[이동층] = True로 방문표시를 한다.

5. 큐가 모두 비었을 때까지 G에 도달하지 못했다면 "use the stairs" 문자열을 리턴한다.