728x90
https://www.acmicpc.net/problem/5014
5014번: 스타트링크
첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.
www.acmicpc.net
이 문제는 전형적인 그래프 탐색 문제입니다. BFS 와 DFS 중 적절하게 선택해 풀면 됩니다.
# BFS 쓸거라 deque
from collections import deque
def solution(F, S, G, U, D):
# 선택지
selects = [U, -D]
# 방문한 위치
visited = [1 if floor != S else 0 for floor in range(F+1)]
que = deque([S])
# 버튼 누른 횟수
cnt = 0
while True:
# 목적 층에 방문했다면 끝
if not visited[G]:
return cnt
# 도달할 수 없으면 끝
if not que:
return 'use the stairs'
for _ in range(len(que)):
# 현재 층
now_floor = que.popleft()
for select in selects:
# 다음 예정 층
next_floor = now_floor + select
# 다음 예정 층이 건물 범위 안에 있고 방문 안했을 때
if (next_floor < len(visited) and next_floor > 0) and visited[next_floor]:
que.append(next_floor)
visited[next_floor] = 0
# 버튼 누른 횟수 추가
cnt += 1
F, S, G, U, D = map(int, input().split())
print(solution(F, S, G, U, D))
728x90
'Coding Test > BaekJoon_Python' 카테고리의 다른 글
백준 2573 <빙산> Python (2) | 2023.10.27 |
---|---|
백준 2468 <안전 영역> Python (0) | 2023.10.27 |
백준 2644 <촌수계산> Python (0) | 2023.10.26 |
백준 12865 <평범한 배낭> Python (0) | 2023.10.25 |
백준 2668 <숫자고르기> Python (0) | 2023.10.25 |