[백준]5014번 스타트링크 (Python/파이썬)

1. 문제

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

 

🎈 전체 F 사이즈의 배열에서 시작 노드인 S에서 도착 노드인 G까지의 최단 경로를 구하면 됩니다.

🎈 이때, 현재 노드 X에서 이동은 +U 또는 -D만 가능합니다.

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

 

아니,, 강호는 면접 날 늦잠을 잘 정도면 지원하면 안 되는 사람 아닐까요..?🤦‍♀️

아무튼 1697번 숨바꼭질과 유사하게, 일차원 배열에서의 BFS로 두 노드 간의 최단 경로를 구하면 됩니당
이렇게 쉬운 문제만 나왔으면 ㅎㅎ

---

2. 입/출력

1) 입력

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

 

2) 출력

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다.

만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

 

3) 예제

> 예제 01

# Input
10 1 10 2 1

# Ouput : 6

 

> 예제 02

# Input
100 2 1 1 0

# Output : use the stairs

 

4) Hidden case

강호가 엘리베이터를 타고 이동할 수 없는 경우,

예를 들어 +U와 -D의 조합으로는 F 범위를 넘기거나, G에 절대 도달할 수 없는 경우에는 use the stairs를 출력합니다.

 

만약, S와 G가 같다면(S==G)?

엘리베이터 버튼을 누를 필요 없으니 0을 출력하면 됩니다.

 

저는 S와 G가 동일한 경우를 BFS에서 고려하지 않고 출력하도록 했다가, U/D를 이상하게 고려해서 최단 경로가 어찌저찌 도출되기도 했습니다.

BFS 탐색 이전에 먼저 예외 케이스를 확인하고, 프로그램이 종료하도록 하셔야 틀리지 않습니다!

---

3. 구현 코드

from collections import deque

def bfs(building, dx):
    need_search = deque([S-1])

    while need_search:
        x = need_search.popleft()
        for dx_ in dx:
            nx = x + dx_

            if nx == G - 1: # 도착
                print(building[x])
                exit()

            if (0 <= nx < F) and building[nx] == 0:
                need_search.append(nx)
                building[nx] = building[x] + 1


### Main ###
F, S, G, U, D = map(int, input().split())

#1) 예외 먼저 정리
if S == G:
    print(0)
    exit()

building = [0 for _ in range(F)]
building[G-1] = -1
building[S-1] = 1

#2) 일반적인 경우의 최단경로 출력
dx = [U, -D]
bfs(building, dx)

#3) 도달 불가능한 경우 출력
print("use the stairs")

 

---

문제 출처

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

5014번: 스타트링크