[baekjoon] 백준 5014번(파이썬): 스타트링크

문제

5014번: 스타트링크

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

코드

import sys
from collections import deque


# bfs 탐색
def bfs():
    visited = [1e9] * 1000001
    queue = deque([s])
    visited[s] = 0
    while queue:
        target = queue.popleft()
        
        # 스타트 링크에 도착했으면 버튼을 누른 횟수 출력
        if target == g:
            return visited[target]
        
        # 반복문을 통해 업/다운
        for i in (u, -d):
            # 범위 내에 있고 탐색하지 않았다면 탐색
            if 1 <= i + target <= f and visited[i + target] == 1e9:
                visited[i + target] = min(visited[target] + 1, visited[i + target]) # 위치로 가기 위한 최솟값을 구함.
                queue.append(i + target)
    
    # 스타트 링크에 도착하지 못한다면 str 출력
    return "use the stairs"


# f: 건물 층수
# s: 현재 위치
# g: 스타트 링크 위치
# u: 위로 가는 버튼
# d: 아래로 가는 버튼
f, s, g, u, d = map(int, sys.stdin.readline().split())

print(bfs())

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법