BOJ 5014 - 스타트링크

문제

백준 온라인 저지 - 5014번

풀이 과정

건물의 시작 층과 목표 층이 주어졌으므로 BFS 탐색을 통해 목표 지점에 도달하기 위한 최단 경로를 찾으면 됩니다.

층이 건물을 벗어나는 경우만 주의한다면 무난하게 풀 수 있는 문제입니다.

코드

import sys
from collections import deque

F, S, G, U, D = list(map(int, sys.stdin.readline().split()))


def bfs(start):
    visit = [0 for _ in range(F+1)]
    q = deque()

    visit[start] = 1
    q.append((start, 0))

    while q:
        here, cost = q.popleft()
        if here == G:
            return cost

        for mv in [U, -D]:
            next = here + mv
            if 1 <= next <= F and not visit[next]:
                visit[next] = 1
                q.append((next, cost + 1))

    return -1


def solution():
    ans = bfs(S)
    return ans if ans != -1 else 'use the stairs'


print(solution())