[백준] 5014 스타트링크 (python)

문제 링크

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

접근법 및 사용 알고리즘

문제 내 point

• 눌러야 하는 버튼의 수의 최소값 -> BFS 써야겠다
• up & down 만 가능 -> 1차원 움직임만 존재

코드

from collections import deque

n, start, goal, up, down = map(int, input().split())

arr = [0]*(n+1)
visited = [False]*(n+1)

def bfs(start):
    q = deque([start])
    visited[start] = True
    while q:
        v = q.popleft()
        if v == goal:
            return arr[goal]
        for next in v+up, v-down:
            if 0 < next <= n and not visited[next]:
                visited[next] = True
                arr[next] = arr[v] + 1
                q.append(next)  # 값 추가
    if arr[goal] == 0:
        return "use the stairs"

print(bfs(start))

특징

• 이전 포스팅 했던 문제(백준 1697 숨바꼭질)와 거의 유사
• 숨바꼭질과의 차이점 : 이동 범위
  • 숨바꼭질의 이동 범위는 MAX = 10**6+1
  • 스타트링크의 이동 범위는 총 F층 (코드 내 n)

채점 결과