[BOJ] 스타트링크

---

코드

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

F,S,G,U,D = map(int, input().split())
def bfs(start):
    visited = [0]*(F+1)
    q = deque([(start, 0)])
    visited[start] = 1
    while q:
        cur, time = q.popleft()
        if cur == G:
            print(time)
            return
        if cur+U <= F and not visited[cur+U]:
            visited[cur+U] = 1
            q.append((cur+U, time+1))
        if cur-D > 0 and not visited[cur-D]:
            visited[cur-D] = 1
            q.append((cur-D, time+1))

    print('use the stairs')
        
bfs(S)

결과

풀이 방법

• 너비우선탐색(bfs)을 활용하여 몇 번째 누른 버튼인지 큐에 넣어 카운트하면서 탐색하다가 G에 도달하면 종료한다.
• 한 번 방문한 층은 다시 방문하지 않아도 되므로 visited 배열에 방문여부를 기록한다.

---