[백준/5014] 스타트링크

문제 링크: https://www.acmicpc.net/problem/5014

문제 접근

해당 문제는 BFS를 이용하는 문제이며, BFS는 자식을 어떻게 설정할 것인가가 중요한 것 같다.

해당 문제에서는 자식을 다음 올라갈 층과 다음 내려갈 층을 자식으로 설정했다.

자식을 큐에 넣을 때는 이미 방문했는지, 층 수 범위안 에 들어오는지를 체크했다.

현재 층이 방문하려는 층이면 리턴해주고 큐가 비었는데도 발견하지 못하면 -1을 리턴했다.

소스 코드

from typing import Deque, List, Tuple
from collections import deque


def bfs(param: Tuple[int]) -> int:
  F, S, G, U, D = param

  q: Deque[Tuple[int]] = deque()
  q.append((S, 0))
  visit: List[bool] = [False] * (F + 1)

  while q:
    cur_stair, button_count = q.popleft()

    if visit[cur_stair]:
      continue

    visit[cur_stair] = True
    if cur_stair == G:
      return button_count

    up_stair = (cur_stair + U, button_count + 1)
    if up_stair[0] > 0 and up_stair[0] <= F and not visit[up_stair[0]]:
      q.append(up_stair)

    down_stair = (cur_stair - D, button_count + 1)
    if down_stair[0] > 0 and down_stair[0] <= F and not visit[down_stair[0]]:
      q.append(down_stair)
  
  return -1


def get_input() -> Tuple[int]:
  F, S, G, U, D = map(int, input().split(" "))
  return F, S, G, U, D


result = bfs(get_input())
print(result if result != -1 else "use the stairs")