[백준 - Python] 5014 - 스타트링크

0. 문제 링크

 

 

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

---

1. 풀이 방법

 

 

BFS를 사용해서 푸는 문제

현재 층과 목적 층이 같다면 끝

그게 아니라면 U만큼 위로 가거나, D만큼 아래로 가면 됨

범위를 벗어나면 안 되고, 이미 방문한 곳을 또 방문하면 안 됨

---

2. 코드

 

 

from collections import deque

F, S, G, U, D = map(int, input().split())
if S == G: print(0), exit(0)        # 현재 층과 목적지가 같다면 끝
board = [*range(0, F + 1)]
board[S] = 0
dy = [U, -D]        # U만큼 위로 가거나, D만큼 아래로 가는 것
dq = deque([[S, 0]])
while dq:
    y, cnt = dq.popleft()
    for i in range(2):
        ny = y + dy[i]
        if ny < 1 or ny > F or board[ny] == 0:      # 범위를 벗어나거나, 이미 방문한 층이라면
            continue
        if ny == G:     # 목적지에 도착했다면
            print(cnt + 1), exit(0)
        dq.append([ny, cnt + 1])
        board[ny] = 0       # 방문 표시
print("use the stairs")

---

3. 마무리

 

 

쉬웠음

다만 목적지에 도착했다는 표시를 큐에서 빼낸 직후에 해야 할 지, 큐에 넣을 좌표를 해야 할 지 분명히 해야 함

큐에 넣을 좌표로 처리한다면 시작과 동시에 최종 조건과 검사해봐야함