[백준 5014번] 스타트링크 - python

문제링크 

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

5014번: 스타트링크

풀이

- 간단한 bfs 문제 

- D 만큼 아래로 이동했을 때 방문하지 않았고 존재하는 층, 즉 0층보다 크면 이동할 수 있으므로 큐에 삽입, cnt + 1, 방문 표시 

  U만큼 위로 이동했을 때 방문하지 않았고 존재하는 층, 즉 F+1층보다 작으면 이동할 수 있으므로 큐에 삽입, cnt + 1, 방문 표시

  위 두 조건을 아무것도 만족시키지 않으면 이동할 수 없으므로 넘어감 

- G에 도착했으면 cnt 리턴, G에 이동하지 않았는데 더이상 이동할 수 없으면 -1 리턴 

from collections import deque 

def bfs(start):
    visited[start] = True 
    
    q = deque()
    q.append((start, 0))

    while q :
        x, cnt = q.popleft()
        
        # g에 도착했으면 
        if x == g :
            return cnt 
            
        # 아래로 이동할 수 있으면 
        if (x - d > 0 and not visited[x-d]) :
            q.append((x-d, cnt + 1 ))
            visited[x-d] = True
        # 위로 이동할 수 있으면 
        if (x + u < f + 1 and not visited[x+u]) :
            q.append((x+u,cnt+1))
            visited[x+u] = True
    
    return -1 
            
f, s, g, u, d = map(int,input().split())

visited = [False] *  (f + 1)
visited[s] = True
result = bfs(s)

if result == -1:
    print("use the stairs")
else:
    print(result)