[BOJ] 5014 / 스타트링크 / Python 파이썬

[BOJ] 5014 / 스타트링크 / Python 파이썬

[BOJ] 5014 / 스타트링크 / Python 파이썬

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

 

풀이

최단거리 구하기 문제로 BFS를 사용하여 풀었다.

 

처음의 시도에서는 시간초과가 계속 발생 하였는데, 이것은 queue 에 추가하기 전에 visited check 를 하는것으로 해결하였다.

queue 에서 꺼낼때 visited check 를 하는것이 경우의 수가 더 많기 때문이었다.

 

※ 전혀 고려하지 못하였던 부분이라 새롭게 공부하게 되었다.

 

from collections import deque

F, S, G, U, D = map(int, input().split())

# 가장 높은 층은 F층이다.
# 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.
# U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다.
# (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

queue = deque()
queue.append((S, 0))

visited = [0] * (F+1)
visited[S] = 1
res = F
while queue:
    s, cnt = queue.popleft()

    # 경우의 수가 더 많아진다.
    # visited[s] = 1
    if s == G:
        res = min(res, cnt)
        break

    if s + U <= F and not visited[s+U]:
        visited[s+U] = 1
        queue.append((s+U, cnt+1))

    if s - D >= 1 and not visited[s-D]:
        visited[s-D] = 1
        queue.append((s-D, cnt+1))


if res == F:
    print("use the stairs")
else:
    print(res)