[백준/파이썬] 5014 스타트링크

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

알고리즘 분류

• BFS

문제풀이

시작점에서부터 시작해서 올라갈 수 있으면 올라가고 내려갈 수 있으면 내려간다.

각각 횟수 값을 방문한 적이 없을 때만 visited에 넣어준다.
ex)
deque([3])
[0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0]
1
deque([5, 2])
[0, 1, 3, 2, 0, 3, 0, 0, 0, 0, 0]
3
deque([2, 7, 4])
[0, 1, 3, 2, 4, 3, 0, 4, 0, 0, 0]
5
deque([7, 4])
[0, 1, 3, 2, 4, 3, 0, 4, 0, 0, 0]
2
deque([4, 9, 6])
[0, 1, 3, 2, 4, 3, 5, 4, 0, 5, 0]
7
deque([9, 6])
[0, 1, 3, 2, 4, 3, 5, 4, 0, 5, 0]
4
deque([6, 8])
[0, 1, 3, 2, 4, 3, 5, 4, 6, 5, 0]
9
deque([8])
[0, 1, 3, 2, 4, 3, 5, 4, 6, 5, 0]
6
deque([10])
[0, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7]
8

그리고 도착지점에 해당하는 그 값을(횟수라서 -1) 출력.

소스코드

from collections import deque

def bfs():
  queue=deque()
  queue.append(s)
  visited[s]=1
  
  while queue:
    now=queue.popleft()
    if now==g:
      return visited[g]

    up=now+u
    down=now-d 
    if up<=f and not visited[up]:
      visited[up]=visited[now]+1
      queue.append(up)
    if down>=1 and not visited[down]:
      visited[down]=visited[now]+1
      queue.append(down)

  return -1

f,s,g,u,d=list(map(int, input().split()))
visited=[0 for _ in range(f+1)]

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

 참고: https://deok2kim.tistory.com/148