[탐색/BFS] 백준 5014 스타트링크 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

5014번: 스타트링크

 

 

 

2. 문제 풀이

 1층부터 F층까지 있는 건물에서 엘리베이터를 타고 S층에서 G층으로 가는 문제입니다.

 엘리베이터는 U층만큼 오르며, D층만큼 내려갑니다. G층으로 가기위해 필요한 최소 버튼 횟수를 구해야 합니다.

 (G층에 갈 수 없을 시, use the stairs를 출력합니다.)

 

2022.02.24 - [Algorithm] - [탐색/BFS] 백준 1697 숨바꼭질 - Python

[탐색/BFS] 백준 1697 숨바꼭질 - Python

 BFS문제로, 백준 1697 숨바꼭질 문제와 유사합니다.

 

 

 

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

F, S, G, U, D = map(int, input().split())   # 층수, 출발지, 목적지, U/D층씩 상승
graph = [[] for _ in range(F+1)] # 정점의 개수 = 층 수

queue = deque([S]) #인접 노드를 저장할 Queue
dist = [0] * (F+1) #횟수 기록

#모든 노드를 탐색할 때까지 반복
while queue:
    #방문 노드
    x = queue.popleft()
    
    #도착 지점이라면 탐색 종료
    if x == G:
        print(dist[x])
        break

    # x에서 +U 또는 -D를 탐색
    for nextX in (x+U, x-D):
        # U나 D가 0이라면 패스
        if nextX == x:
            continue;
        # 0~100000지점 내이고, 방문하지 않았다면
        if 1 <= nextX <= F and not dist[nextX]:
            dist[nextX] = dist[x] + 1 #방문하고 횟수 1늘림
            queue.append(nextX) #큐에 추가

#해당 경우 없음
else:
    print("use the stairs")

 올라가는 경우와 내려가는 경우를 계속해서 탐색하며, 최소 횟수를 구합니다.

 이때 U 혹은 D가 0인 경우를 주의해야 합니다. 이 경우에는 아무런 행동을 하지 않은 것과 동일한 결과이므로 방문횟수를 높여선 안됩니다.