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

5014번: 스타트링크 (acmicpc.net)

5014번: 스타트링크

 

BFS 문제이다

 

엘레베이터를 타고 올라가든 내려가든 버튼을 누르는 횟수는 1로 동일하기 때문에 (=가중치가 1로 똑같기 때문에)

중복방문을 허용하지 않는 BFS 문제라고 생각하면 된다.

버튼을 눌러 얼마만큼 이동하느냐는 로직에 큰 영향을 주지 않는다. 범위만 넘어가지 않도록 설정해주면 된다.

 

가중치가 여러 개여서 중복방문을 허용하는 문제👇

2021.03.18 - [Algorithm/Graph] - [백준 BOJ] 13549 숨바꼭질3 (Python)

[백준 BOJ] 13549 숨바꼭질3 (Python)

from collections import deque


def bfs(start):
    q = deque([start])

    cnt = [-1] * f
    cnt[start] = 0

    while q:
        cur_floor = q.popleft()

        if cur_floor == g - 1:			# 도착하면 현재까지 누른 횟수를 반환
            return cnt[cur_floor]

        for i in range(2):
            if i == 0:
                next_floor = cur_floor + u
            else:
                next_floor = cur_floor - d

            if not 0 <= next_floor < f or cnt[next_floor] != -1:# 범위, 방문 여부 체크
                continue

            q.append(next_floor)
            cnt[next_floor] = cnt[cur_floor] + 1

    return 'use the stairs'				# 탐색을 다 해도 도착 못하면 문자열 반환


f, s, g, u, d = map(int, input().split())
print(bfs(s - 1))