Problem Solving/Baekjoon Online Judge
[BOJ/백준] 5014번 스타트링크 | BFS | 파이썬
Donghae
2022. 5. 4. 20:51
문제

풀이
from collections import deque
F, S, G, U, D = map(int, input().split())
visited = [0] * (F + 1)
def bfs(visited, v):
queue = deque([v])
dx = [U, - D]
while queue:
x = queue.popleft()
if x == G:
break
for i in range(len(dx)):
# 해당하는 층이 없을 때 움직이지 않는다
if dx[i] == 0:
continue
nx = x + dx[i]
if 0 < nx <= F and not visited[nx]:
visited[nx] = visited[x] + 1
queue.append(nx)
if S == G:
print(0)
else:
bfs(visited, S)
if visited[G]:
print(visited[G])
else:
print('use the stairs')
현재 위치에서 스타트 링크의 위치까지, 가까운 곳 부터 방문하며 최단거리(버튼을 적어도 몇 번 눌러야 하는지)를 확인해야한다. 즉 1차원 BFS문제이다.
주의해야할 점
- 현재 위치와 스타트 링크의 위치가 같은 경우 > 엘리베이터 버튼을 누르지 않아도 된다.
- U또는 D가 0인 경우 > 역시 엘리베이터 버튼을 누르지 않아도 된다(반복문에서 continue)
5014번: 스타트링크
첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.
www.acmicpc.net
okky에서 알고리즘 스터디를 구했다. 이제 알고리즘 풀이도 외롭지않아😇