백준: 5014 스타트링크

문제

5014번: 스타트링크

 

문제 풀이

 문제에 F, S, G, U, D `(건물의 높이, 시작층, 가고자 하는 층, 한 번에 올라가는 층, 한 번에 내려가는 층)`가 주어진다. 시작 층에서 엘리베이터를 이용해 가고자 하는 층에 도달하는 최소 경우를 반환하는 문제이다. 만약 도달할 수 없다면 계단을 이용하라는 메시지를 출력한다.

 

• BFS를 통해 시작층 부터 올라가는 경우, 내려가는 경우를 탐색한다.
  • 올라가는 경우 F보다 작거나 같아야 하며, 내려가는 경우는 0 보다 커야 한다.
• 재방문을 막기 위해 현재 방문한 층을 `visited` 리스트를 통해 체크한다.
• 최소값을 카운트하기 위한 방법은 3가지가 있다.
  • q에 방문할 다른 층과 카운트를 함께 추가하기.
    • `q.append((next_floor, cnt + 1))`
  • visited를 이용하여 방문 횟수를 누적하기
    • `visited[next_floor] = visited[cur_floor] + 1`
  • 현재 추가된 큐를 하나의 카운트로 취급하기
    • 토마토 문제와 같은 방식.

 

코드

from sys import stdin
from collections import deque


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

    while q:
        cur_floor, cnt = q.popleft()

        if cur_floor == g:
            return cnt

        for next_floor in cur_floor + u, cur_floor - d:
            if 0 < next_floor <= f and not visited[next_floor]:
                q.append((next_floor, cnt + 1))
                visited[next_floor] = True
    return "use the stairs"


if __name__ == '__main__':
    f, s, g, u, d = map(int, stdin.readline().split())
    visited = [False] * (f + 1)
    print(bfs([s, 0]))