❓ 문제
백준 실버1 문제 > 스타트링크
❗ 해결
조금만 읽어보니 BFS 문제다.
1부터 10까지 있고, 내가 10이라는 포인트를 가고 싶다.
현재 위치는 1이고 나는 한번에 앞으로 2칸 가거나 뒤로 1칸 밖에 못간다.
해당 포인트까지 가는 최소 횟수를 구해라
이렇게 문제를 바꿔 보았다.
그러면, 2차원 BFS가 아니고 1차원 BFS가 된다.
처음에 입력값을 받고
방문했던 곳을 체크할 visited 리스트와, 방문 횟수를 누적해줄 check라는 리스트를 선언해준다.
from collections import deque
f,s,g,u,d = map(int, input().split())
visited = [0] * (f+1)
check = [0] * (f+1)그리고 시작할 층이 정해져 있다.
queue = deque([s])
directions = [u, -d]
visited[s] = 1
check[s] = 1시작할 층을 큐에 처음 넣어 준다.
방향은 위, 아래 두개밖에 없다.
while queue:
current = queue.popleft()
for i in range(2):
move = current + directions[i]
if 0 < move <= f and visited[move] == 0:
visited[move] = 1
check[move] = check[current] + 1
queue.append(move)큐를 반복하면서 건물 범위에 벗어나지 않고 방문하지 않은 곳이면 해당 위치를 방문해준다.
from collections import deque
f,s,g,u,d = map(int, input().split())
visited = [0] * (f+1)
check = [0] * (f+1)
queue = deque([s])
visited[s] = 1
check[s] = 1
directions = [u, -d]
while queue:
current = queue.popleft()
for i in range(2):
move = current + directions[i]
if 0 < move <= f and visited[move] == 0:
visited[move] = 1
check[move] = check[current] + 1
queue.append(move)
if check[g] == 0:
print('use the stairs')
else:
print(check[g] - 1)
마지막에 현재 층에서 check를 1로 해줬으니 빼주고 출력한다.
만약 check[g]가 0이면 엘리베이터로 갈 수 없는 곳이라고 간주 한다.
