문제
접근
1차원 BFS 문제이다.
위, 아래로만 이동할 수 있는 1차원 선에서 움직인다고 생각하면 된다.
역시 BFS는 몇 번만에 해당 지점에 도착했는지 파악이 쉽고, 처음 도착했을 때 횟수가 최소임을 보장받는다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import deque
def bfs(start, end):
dx = [up, -down]
q = deque()
q.append(start)
while q:
now = q.popleft()
if now == end:
return board[now]-1
for x in dx:
moved = x + now
if moved < 1 or moved > n:
continue
if board[moved] == 0:
board[moved] = board[now]+1
q.append(moved)
return 'use the stairs'
n, start, end, up, down = map(int, input().split(' '))
board = [0]*(n+1)
board[0] = -1
board[start] = 1
ans = bfs(start, end)
print(ans)