[백준|파이썬] 5014: 스타트링크 (실버1)

문제

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

5014번: 스타트링크

 

 

🐍파이썬

import sys
from collections import deque

def bfs(x):
    queue = deque([x])
    tower[x] = 0
    while queue:
        x = queue.popleft()
        if x == g:
            return tower[x]
        for nx in [x+u, x-d]:
            if nx > f or nx <= 0:
                continue
            if tower[nx] == -1:
                tower[nx] = tower[x] + 1
                queue.append(nx)
    return "use the stairs"

f, s, g, u, d = map(int, sys.stdin.readline().split())
tower = [-1] * (f+1)
print(bfs(s))

1697: 숨바꼭질(파이썬) 과 동일한 방식으로 풀었다. 

1️⃣ tower라는 리스트를 건물의 층수만큼 -1로 초기화해 주었다. 이때 배열의 인덱스와 층수를 동일하게 만들기 위해 배열의 원소는 f+1개로 설정해주었다.

ex) f = 5 라면, 배열의 원소는 [ -1, -1, -1, -1, -1, -1 ]이고 인덱스 0은 사용하지 않는다.

2️⃣ 강호의 위치 s에서부터 bfs를 실행한다. 강호가 방문한 tower[s]는 0으로 초기화해 다시 방문하지 않게 해준다.

3️⃣ 큐에서 방문할 수 있는 위치를 하나하나 방문한다. 위층으로 올라가는 경우의 좌표인 x+u와 아래층으로 내려가는 경우의 좌표인 x-d를 모두 방문하되, 배열의 범위를 벗어나 에러를 발생시킬 수 있는 경우의 수는 제외한다. 추가로 0층이 존재한지 않다고 가정했기 때문에 인덱스 0도 방문하지 않도록 해준다.

4️⃣  방문한 좌표의 값은 이전 좌표값 + 1로 설정하면 버튼을 누른 횟수를 체크하는 동시에 방문처리도 진행할 수 있다.(tower[nx] == -1인 경우에만 방문하기 때문)

5️⃣ 만약 큐에 저장된 값이 g(스타트링크 사무실)와 동일하다면, 목적지에 도달했다는 뜻이므로 현재 좌표의 값(버튼을 누른 총 횟수)를 리턴한다.