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