[백준] 5014번: 스타트링크 - 파이썬

🧩문제 해석

F = 스타트링크 건물 층의 총 계수
S = 현재 강호의 위치
G = 스타트링크의 위치
U = 위로 올라가는 엘레베이터 층의 간격
D = 아래로 내려가는 엘레베이터 층의 간격

위 사항들이 주어졌을 때, 현재 강호의 위치에서 스타트링크의 위치로 엘레베이터로 가려 할 때, 누른 버튼의 최소값을 출력하는 문제이다. 만약 도달할 수 없다면, 계단 이용하라는 문장을 출력한다.

모든 층을 돌아다닐 필요가 없고 목표층에 도달하면 엘레베이터를 멈추면 되니까 BFS가 효율적이다. 

 

📕 풀이

BFS로 풀었다.
이동할 수 있는 층은 [현재 위치 + U, 현재 위치 -D] 를 통해 유추하였고, 이 데이터가 F 안에 있고, 방문한 적이 없다면, 그 층으로 방문하였다.

 

💻 코드

from collections import deque
f,s,g,u,d = map(int, input().split())

# f= 총 층의 계수
# s=  강호의 위치층
# g= 스타트링크의 위치
# u= 위로 갈수 있는 층
# d= 아래로 갈 수 있는 층
# 가능하다면 누른 버튼 최소값
# 불가하다면 use the stairs

visited = [False for i in range(f+1)] # 방문체크
def bfs():
    queue = deque()
    queue.append((s, 0)) # 시작위치와 카운트 체크
    while queue: # 큐가 빌때까지
        now, cnt = queue.popleft()
        candi = [now+u, now-d] # 이동가능 위치
        for i in candi:
            if 0 < i <= f: # f 안에 있다면
                if not visited[i]: # 방문하지 않았다면
                    visited[i] = True # 방문 처리
                    queue.append((i, cnt+1)) # 큐에 삽입
                    if i == g: # 만약 현재 이동 위치가 스타트링크의 위치라면
                        return cnt+1 # 이동횟수 출력
    return "use the stairs" # 큐가 빌때까지 찾지 못했다면, 계단 이용하시오.
if s == g: # 시작부터 강호의 위치가 스타트링크의 위치라면 이동안함
    print(0)
else: # 이동시작 함수 호출
    visited[s] = True # 현재 위치 방문처리
    print(bfs())

 

🔗 문제링크 : 스타트링크

5014번: 스타트링크

너비 우선 탐색