5014_스타트링크

▶ 실버 1 (BFS)

풀이

현재 층에서 이동하는 경우는 1) 올라가거나, 2) 내려가거나 둘 중 하나입니다.

또한, 도착 층까지의 최단 경로를 찾는 것이기 때문에 BFS를 사용했습니다.

 

주의할 점

1. 다음 층이 1부터 f 이하여야합니다.

2. 이미 방문한 층은 그 경로가 최소이기 때문에 갱신할 필요가 없습니다. 그래서 BFS와 동일하게 visited 배열로 방문여부를 확인해주면 됩니다.

 

코드

# 5014_스타트링크
from collections import deque
import sys
input = sys.stdin.readline()

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

def BFS(f, s, g, u, d):
    if s == g:
        return 0

    queue = deque([(s, 0)])  # (현재 층, 버튼 클릭 횟수)
    visited = set()
    visited.add(s)

    while queue:
        cur, cnt = queue.popleft()

        for next in (cur + u, cur - d):
            if 1 <= next <= f and next not in visited:
                if next == g:
                    return cnt + 1
                queue.append((next, cnt + 1))
                visited.add(next)

    return "use the stairs"

print(BFS(f, s, g, u, d))