[python] 백준 - 5014 (스타트링크)
실버1 문제이며, 제한 시간은 1초이다.
문제
해결 과정
문제를 처음 읽었을 때는 그리디..? 라는 생각이 들 수 있다. 하지만 그래프 탐색으로 풀면 훨씬 쉽게 풀린다. BFS로 구현하며 위로 올라가는 경우와 아래로 내려가는 경우를 모두 큐에 넣고 돌리면서 목표 층에 도달했을 경우 멈추는 방식으로 구현했다.
풀이
from collections import deque
def bfs(s):
queue = deque()
queue.append(s)
visited[s] = 1
while queue:
x = queue.popleft()
if x == g:
return True
for i in range(2):
nx = x + dx[i]
if 1 <= nx <= f and visited[nx] == 0:
queue.append(nx)
visited[nx] = visited[x] + 1
return False
f, s, g, u, d = map(int, input().split())
visited = [0] * (f + 1)
dx = [u, -d]
if bfs(s):
print(visited[g] - 1)
else:
print('use the stairs')어렵지 않은 문제였다!
댓글
0아직 댓글이 없습니다.